We construct models with minimal field content that can simultaneously explain the muon g-2 anomaly and give the correct dark matter relic abundance. These models fall into two general classes, whether or not the new fields couple to the Higgs. For the general structure of models without new Higgs couplings, we provide analytical expressions that only depend on the $SU(2)_L$ representation. These results allow to demonstrate that only few models in this class can simultaneously explain $(g-2)_mu$ and account for the relic abundance. The experimental constraints and perturbativity considerations exclude all such models, apart from a few fine-tuned regions in the parameter space, with new states in the few 100 GeV range. In the models with new Higgs couplings, the new states can be parametrically heavier by a factor $sqrt{1/y_mu}$, with $y_mu$ the muon Yukawa coupling, resulting in masses for the new states in the TeV regime. At present these models are not well constrained experimentally, which we illustrate on two representative examples.