Using first-principles approaches we find that the Auger recombination in PbSe is anomalous in three distinct ways. First, the direct Auger coefficient is 4 orders of magnitude lower than that of other semiconductors with similar band gaps, a result that can be attributed to the lack of involvement of a heavy-hole band. Second, phonon-assisted indirect Auger recombination prevails, contrary to the common belief that direct Auger is dominant in narrow-gap semiconductors. Third, an unexpectedly weak temperature dependence of the Auger coefficient is observed, which we can now attribute to the indirect nature of the Auger process. The widely accepted explanation of this behavior in terms of an unusual temperature dependence of the band gap is only a secondary effect. Our results elucidate the mechanisms underlying the anomalous Auger recombination in IV-VI semiconductors in general, which is critical for understanding and engineering carrier transport.