We report the first detection of pure rotational transitions of TiO and TiO2 at (sub-)millimeter wavelengths towards the red supergiant VYCMa. A rotational temperature, Trot, of about 250K was derived for TiO2. Although Trot was not well constrained for TiO, it is likely somewhat higher than that of TiO2. 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 TiO2 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.