Three dimensional materials with strong spin-orbit coupling and magnetic interactions represent an opportunity to realize a variety of rare and potentially useful topological phases. In this work, we use first principles calculations to show that the recently synthesized material Bi2MnSe4 displays a combination of band inversion and magnetic interactions, leading to several topological phases. Bi2PbSe4, also studied, also displays band inversion and is a topological insulator. In bulk form, the ferromagnetic phase of Bi2MnSe4 is either a nodal line or Weyl semimetal, depending on the direction of the spins. When the spins are arranged in a layered antiferromagnetic configuration, the combination of time reversal plus a partial translation is a new symmetry, and the material instead becomes an antiferromagnetic topological insulator. However, the intrinsic TRS breaking at the surface of Bi2MnSe4 removes the typical Dirac cone feature, allowing the observation of the half-integer quantum anomalous Hall effect (AHC). Furthermore, we show that in thin film form, for some thicknesses, Bi2MnSe4 becomes a Chern insulator with a band gap of up to 58 meV. This combination of properties in a stoichiometric magnetic material makes Bi2MnSe4 an excellent candidate for displaying robust topological behavior.