We have searched for neutrinoless tau lepton decays into l and V-0, where l stands for an electron or muon, and V-0 for a vector meson (phi, omega, K*(0), (K) over bar*(0) or rho(0)), using 543 fb(-1) of data collected with the Belle detector at the KEKB