A search for dark matter is performed by looking for events in pp collisions with large missing transverse momentum and a recoiling Higgs boson that decays to either a pair of photons or a pair of tau leptons. The data correspond to an integrated luminosity of 35.9~\mathrm{fb}^{-1} collected in 2016 by the CMS experiment at the CERN LHC at a center-of-mass energy of 13~\mathrm{TeV}. No significant excess over the expected standard model background is observed. Results are interpreted in the context of two benchmark simplified models. Upper limits with confidence level are presented for the signal production cross section times branching fraction. Results are also interpreted in terms of confidence level limits on the spin-independent dark matter-nucleon cross section as a function of dark matter mass. This is the first search for dark matter produced in association with a Higgs boson decaying to two tau leptons.