We report a surface treatment that systematically improves the quality factor of niobium radio frequency cavities beyond the expected limit for niobium. A combination of annealing in a partial pressure of nitrogen or argon gas and subsequent electropolishing of the niobium cavity surface leads to unprecedented low values of the microwave surface resistance, and an improvement in the efficiency of the accelerating structures up to a factor of 3, reducing the cryogenic load of superconducting cavities for both pulsed and continuous duty cycles. The field dependence of the surface resistance is reversed compared to standardly treated niobium.