We report on a search for Interstellar CH2D+. Four transitions occur in easily accessible portions of the spectrum; we report on emission at the frequencies of these transitions toward high column density star-forming regions. While the observations can be interpreted as being consistent with a detection of the molecule, further observations will be needed to secure that identification. The CH2D+ rotational spectrum has not been measured to high accuracy. Lines are weak, as the dipole moment induced by the inclusion of deuterium in the molecule is small. Astronomical detection is favored by observations toward strongly deuterium-fractionated sources. However, enhanced deuteration is expected to be most significant at low temperatures. The sparseness of the available spectrum and the low excitation in regions of high fractionation make secure identification of CH2D+ difficult. Nonetheless, owing to the importance of CH3+ to interstellar chemistry, and the lack of rotational transitions of that molecule owing to its planar symmetric structure, a measure of its abundance would provide key data to astrochemical models.