In regions of large tan β and small mA, searches for heavy neutral minimal supersymmetric standard model (MSSM) Higgs bosons at the Tevatron are promising. At the same time, rates in direct dark matter experiments, such as CDMS, are enhanced in the case of large tan β and small mA. As a result, there is a natural interplay between the heavy, neutral Higgs searches at the Tevatron and the region of parameter space explored by CDMS. We show that if the lightest neutralino makes up the dark matter of our universe, current limits from CDMS strongly constrain the prospects of heavy, neutral MSSM Higgs discovery at the Tevatron unless |μ| 400GeV. The limits of CDMS projected for 2007 will increase this constraint to |μ| 800GeV. If CDMS does observe neutralinos in the near future, however, it will make the discovery of Higgs bosons at the Tevatron far more likely.