The results are reported on a precise crystal structure and microstructure determination of new mixed YVO4-based orthovanadates of Y0.5R0.5VO4 (R = Sm, Tb, Dy, Ho, Tm, Yb, Lu) as well as some Bi3+-doped RVO4 (R = La, Gd, Y, Lu) nano- (submicro-) materials. The formation of continuous solid solutions in the YVO4–RVO4 pseudo-binary systems (R = Sm, Tb, Dy, Ho, Tm, Yb, Lu) has been proved. The lattice constants and unit cell volumes of the new mixed orthovanadates were analyzed as a function of R3+ cation radius. The impact of crystal structure parameters on the energy band gap of the materials was studied by means of photoluminescence studies of the Bi3+-doped compounds.