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.