This paper introduces a new approximation method for the time-harmonic Maxwell equations. This method belongs to the family of negative-norm least-squares algorithms for electromagnetic problems, as introduced in [BP] and further developed in [BKP]. The advantages of our approach include the fact that it is based on a natural weak variational formulation which avoids the use of Nedelec elements as well as the introduction of potentials and ``gauge conditions''. The magnetic and electric fields are simultaneously approximated, in contrast to many methods where one of the unknowns is eliminated and is later computed by differentiation of the approximate solution. Finally, the resulting numerical algorithm can be efficiently implemented and has an optimal convergence rate even for problems with low regularity.