We report the results of a systematic study of the catalytic activity of mass-selected vanadium oxide clusters deposited on rutile TiO2 surfaces under ultrahigh vacuum (UHV) conditions. Our results show that supported V, VO, and VO2 clusters are not catalytically active for the oxidative dehydrogenation of methanol to formaldehyde but can be made catalytically active by postoxidation. In addition, we found that the postoxidized VO/TiO2 produces the most formaldehyde. Scanning tunneling microscopy (STM) imaging of the postoxidized VO/TiO2 reveals isolated clusters with height and width indicative of VO3 bound to the TiO2 surface. Our results are consistent with previous density functional theory (DFT) calculations that predict that VO3 will be produced by postoxidation of VO and that VO3/TiO2 is an active catalyst.