To understand the structure-reactivity relationships for mixed-metal oxide catalysts, well-defined systems are required. Mixtures of vanadia and titania (TiO2) are of particular interest for application in heterogeneous catalysis, with TiO2 often acting as the support. By utilizing high-resolution scanning tunneling microscopy, we studied the interaction of vanadium (V) with the anatase TiO2(101) surface in the sub-monolayer regime. At 80 K, metallic V nucleates into homogeneously distributed clusters onto the terraces with no preference for nucleation at the step edges. However, embedding of single V atoms into TiO2 occurs following annealing at room temperature. In conjunction with X-ray photoelectron spectroscopy data and density functional theory calculations, we propose that monomeric V atoms occupy positions of regular surface Ti sites, i.e., Ti atoms are substituted by V atoms.