We report results from a search for production of a neutral Higgs boson in association with a $b$ quark. We search for Higgs decays to $\tau$ pairs with one $\tau$ subsequently decaying to a muon and the other to hadrons. The data correspond to 2.7fb$^{-1}$ of $\ppbar$ collisions recorded by the D0 detector at $\sqrt{s} = 1.96$TeV. The data are found to be consistent with background predictions. The result allows us to exclude a significant region of parameter space of the minimal supersymmetric model.