A new series of cubic double perovskites Ba$_2R_{2/3}$TeO$_6$ ($R$ = Y, La, Pr, Nd, Sm-Lu) was synthesized via solid state reaction. The $R^{3+}$ and Te$^{6+}$ ions are ordered on alternating octahedral sites, with the rare earth sites 2/3 occupied to balance the charge. The lattice parameters decrease monotonically from a = 8.5533(3) {AA} for Ba$_2$La$_{2/3}$TeO$_6$ to a = 8.3310(4) {AA} for Ba$_2$Lu$_{2/3}$TeO$_6$. The lattice parameter for $R$ = Y is close to that of Ho. Analysis of the resulting bond lengths indicates a structural relaxation around the $R$ ion site. Ba$_2$La$_{2/3}$TeO$_6$, Ba$_2$Y$_{2/3}$TeO$_6$ and Ba$_2$Lu$_{2/3}$TeO$_6$ show primarily temperature-independent magnetic susceptibility due to the lack of a local rare earth moment. For Ba$_2$Sm$_{2/3}$TeO$_6$ and Ba$_2$Eu$_{2/3}$TeO$_6$, the susceptibilities are influenced by Van Vleck-like contributions from excited state multiplets. For the remaining members, the Curie-Weiss law is followed with low-temperature deviations that can be associated with various degrees of crystalline electric field splitting. No magnetic ordering was observed down to 1.8 K in any of the compounds.