A novel series of microwave dielectric ceramics (Na0.5xBi0.5xCa1-x)MoO4 (0 ≤ x ≤ 0.6) was synthesized by the solid state reaction method. The crystal structures, microstructures, dielectric responses, and vibrational properties were investigated using X-ray diffraction, scanning electron microscopy, a microwave network analyzer, and terahertz, Raman and infrared spectroscopies. All the samples could be sintered well below 850 °C and a scheelite solid solution could be formed without any secondary phase. At x = 0.5 and x = 0.6, low-firing (750-775 °C) high performance microwave dielectric materials were obtained with permittivities of 19.1-21.9, Q × f values of 20 660-22 700 GHz, and near-zero temperature coefficients. The factors affecting microwave dielectric properties were discussed based on the vibrational data. As revealed by Raman spectroscopy, the disorder degree grows with x rising, which might increase the permittivities and decrease the Q × f values. The infrared spectra were analyzed using the classical harmonic oscillator model, and the complex dielectric responses gained from the fits were extrapolated down to the microwave and THz range. It is believed that the external vibration modes located at low frequencies dominate the main dielectric polarization contributions, especially the Na-O/Bi-O translational mode. This result indicates that the microwave dielectric properties of (Na0.5xBi0.5xCa1-x)MoO4 ceramics mainly depend on the behavior of AO8 polyhedra.