  We extend previous combinations of LEP and cosmological relic density
constraints on the parameter space of the constrained MSSM, with universal
input supersymmetry-breaking parameters, to large tan beta. We take account of
the possibility that the lightest Higgs boson might weigh about 115 GeV, but
also retain the possibility that it might be heavier. We include the most
recent implementation of the b to s gamma constraint at large tan beta. We
refine previous relic density calculations at large tan beta by combining a
careful treatment of the direct-channel Higgs poles in annihilation of pairs of
neutralinos chi with a complete treatment of chi - stau coannihilation, and
discuss carefully uncertainties associated with the mass of the b quark. We
find that coannihilation and pole annihilations allow the CMSSM to yield an
acceptable relic density at large tan beta, but it is consistent with all the
constraints only if m_chi > 140 (180) GeV for mu > 0 (mu < 0) for our default
choices m_b(m_b) = 4.25 GeV, m_t = 175 GeV, and A_0 = 0.
