We study electroweak scale Dark Matter (DM) whose interactions with baryonic matter are mediated by a heavy anomalous $Z$. We emphasize that when the DM is a Majorana particle, its low-velocity annihilations are dominated by loop suppressed annihilations into the gauge bosons, rather than by p-wave or chirally suppressed annihilations into the SM fermions. Because the $Z$ is anomalous, these kinds of DM models can be realized only as effective field theories (EFTs) with a well-defined cutoff, where heavy spectator fermions restore gauge invariance at high energies. We formulate these EFTs, estimate their cutoff and properly take into account the effect of the Chern-Simons terms one obtains after the spectator fermions are integrated out. We find that, while for light DM collider and direct detection experiments usually provide the strongest bounds, the bounds at higher masses are heavily dominated by indirect detection experiments, due to strong annihilation into $W^+W^-$, $ZZ$, $Zgamma$ and possibly into $gg$ and $gammagamma$. We emphasize that these annihilation channels are generically significant because of the structure of the EFT, and therefore these models are prone to strong indirect detection constraints. Even though we focus on selected $Z$ models for illustrative purposes, our setup is completely generic and can be used for analyzing the predictions of any anomalous $Z$-mediated DM model with arbitrary charges.