We developed a new chemical strategy to enhance the stability of lead selenide nanocrystals (PbSe NCs) against oxidation through the surface passivation by P-O- moieties. In the synthesis of PbSe NCs, tris(diethylamino)phosphine (TDP) selenide (Se) was used as a Se precursor, and the resulting PbSe NCs withstood long-term air exposure while showing nearly no sign of oxidation. Nuclear magnetic resonance (NMR) spectroscopy reveals that TDP derivatives passivate the surface of PbSe NC. Through a series of ligand cleavage reactions, we found that the TDP derivatives are bound on NC surface through the P-O- moiety. Based on such understanding, it turned out that direct addition of various PAs during the synthesis of PbSe NCs also results in the NCs whose absorption spectrum remains nearly intact after air exposure for weeks. The P-O- moieties render the NCs stable in the operation of field effect transistors, suggesting that our findings can enable the use of air stable PbSe NCs in wider array of optoelectronic applications.