The thermal relic density of neutralino dark matter in the brane world cosmology is studied. Since the expansion law at a high energy regime in the brane world cosmology is modified from the one in the standard cosmology, the resultant relic density can be altered. It has been found that, if the five-dimensional Planck mass M-5 is lower than 10(4) TeV, the brane world cosmological effect is significant at the decoupling time, and the resultant relic density is enhanced. We calculate the neutralino relic density in the constrained minimal supersymmetric standard model and show that the allowed region is dramatically modified from the one in the standard cosmology and eventually disappears as M-5 is decreasing. We also find a new lower bound on M-5 greater than or similar to 600 TeV based on the neutralino dark matter hypothesis, namely, the lower bound in order for the allowed region of neutralino dark matter to exist.