We report the first detection of pure rotational transitions of TiO and TiO2 at (sub-)millimeter wavelengths towards the red supergiant VY CMa. A rotational temperature, Trot, of about 250 K 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. Based on observations carried out with the Submillimeter Array and IRAM Plateau de Bure Interferometer.Plateau de Bure data (FITS file) is only available at the CDS via anonymous ftp to cdsarc.u-strasbg.fr (130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz- bin/qcat?J/A A/551/A113
