Lead-free relaxor ceramics based on sodium-bismuth titanate, (1-x)(Na1/2Bi1/2)TiO3-xLa(Mg1/2Ti1/2)O-3 [(1-x)NBT-xLMT] (0 <= x <= 0.25), were prepared by both the conventional mixed oxide method and by the Pechini route, and their crystal structure and dielectric properties were investigated. All the compositions studied were found to possess a rhombohedrally distorted crystal lattice at room temperature. A distortion degree of the unit cell decreases and its volume increases with LMT content. The temperature of the dielectric permittivity maximum does not change with increasing substitution rate. As x is increased, the frequency-dependent dielectric peaks are flattened. The compositional evolution of structure and dielectric characteristics of the ceramics obtained are analysed and discussed in respect to size, charge and polarizability of the cations involved.