Enhancing the efficiency of thermoelectric materials has been practiced extensively by either improving the power factor or reducing the lattice thermal conductivity. Magnetism, and the magnetic moment-charged carrier interactions, has been suggested to enhance the efficiency of some compounds. Nevertheless, decoupling of the magnetic and the carrier concentration-related effects has never been achieved to prove once and for all, the importance of magnetism in thermoelectricity. Herein, we report improved quality criterion of bismuth telluride upon chromium substitution. The magnetic interactions with the magnetic moment carried by Cr atoms have increased the electrons' effective mass, enhancing the thermopower. Combined with the decrease in the lattice thermal conductivity, the overall performance of these compounds has been enhanced by 25% at constant carrier concentration, an improvement seldom observed. This is a robust enhancement principle because magnetic interactions are effective at high temperatures above the transition temperature, unlike magnon drag which is dependent on ordering and typically a low temperature phenomenon. Our results indicate that taking advantage of such relatively easily implemented magnetic doping effects along with existing strategies can lead to enhanced efficiency of thermoelectric materials.