Microwave dielectric permittivity of NaTaO3 ceramics exhibits increase on cooling and saturation at low temperatures, which is typical for incipient ferroelectrics. The temperature dependence of permittivity was successfully fit with the Barrett formula and explained by polar phonon softening detected in infrared reflectivity and THz transmision spectra. Solid solution of NaTaO3 with Na0.5Bi0.5TiO3 (NBT) exhibits increase of both permittivity and dielectric loss with rising Na0.5Bi0.5TiO3 concentration. This is caused by increasing contribution of dielectric relaxation seen in THz dielectric spectra below phonon frequencies. The relaxation stems from dynamics of polar nanoclusters and ferroelectric domains in NBT.