We discuss the origin of the anti-helium-3 and -4 events possibly detected by AMS-02. Using up-to-date semi-analytical tools, we show that spallation from primary hydrogen and helium nuclei onto the ISM predicts a $overline{{}^3{rm He}}$ flux typically one to two orders of magnitude below the sensitivity of AMS-02 after 5 years, and a $overline{{}^4{rm He}}$ flux roughly 5 orders of magnitude below the AMS-02 sensitivity. We argue that dark matter annihilations face similar difficulties in explaining this event. We then entertain the possibility that these events originate from anti-matter-dominated regions in the form of anti-clouds or anti-stars. In the case of anti-clouds, we show how the isotopic ratio of anti-helium nuclei might suggest that BBN has happened in an inhomogeneous manner, resulting in anti-regions with a anti-baryon-to-photon ratio $bar{eta}simeq10^{-3}eta$. We discuss properties of these regions, as well as relevant constraints on the presence of anti-clouds in our Galaxy. We present constraints from the survival of anti-clouds in the Milky-Way and in the early Universe, as well as from CMB, gamma-ray and cosmic-ray observations. In particular, these require the anti-clouds to be almost free of normal matter. We also discuss an alternative where anti-domains are dominated by surviving anti-stars. We suggest that part of the unindentified sources in the 3FGL catalog can originate from anti-clouds or anti-stars. AMS-02 and GAPS data could further probe this scenario.