We report the first detection of pure rotational transitions of TiO and TiO_2 at (sub-)millimeter wavelengths towards the red supergiant VY CMa. A rotational temperature, T_rot, of about 250 K was derived for TiO_2. Although T_rot was not well constrained for TiO, it is likely somewhat higher than that of TiO_2. The detection of the Ti oxides confirms that they are formed in the circumstellar envelopes of cool oxygen-rich stars and may be the seeds of inorganic-dust formation, but alternative explanations for our observation of TiO and TiO_2 in the cooler regions of the envelope cannot be ruled out at this time. The observations suggest that a significant fraction of the oxides is not converted to dust, but instead remains in the gas phase throughout the outflow.