A search for dark matter pair production in association with a Higgs boson decaying to a pair of bottom quarks is presented, using 3.2 $fb^{-1}$ of $pp$ collisions at a centre-of-mass energy of 13 TeV collected by the ATLAS detector at the LHC. The decay of the Higgs boson is reconstructed as a high-momentum $b\bar{b}$ system with either a pair of small-radius jets, or a single large-radius jet with substructure. The observed data are found to be consistent with the expected backgrounds. Results are interpreted using a simplified model with a $Z'$ gauge boson mediating the interaction between dark matter and the Standard Model as well as a two-Higgs-doublet model containing an additional $Z'$ boson which decays to a Standard Model Higgs boson and a new pseudoscalar Higgs boson, the latter decaying into a pair of dark matter particles.