Here, for the first time, we demonstrate amplified spontaneous emission (ASE) from PbSe nanocrystals (NCs) with emission energies tunable in the near-infrared (IR). We show that despite complications associated with a high, 8-fold degeneracy of the lowest quantized states and fast, nonradiative Auger recombination, optical gain parameters of PbSe NCs are comparable to those of CdSe NCs used for light amplification in the visible. These results indicate that previous unsuccessful attempts to realize the lasing regime in NCs of lead salts were not due to intrinsic physical reasons but likely resulted from material quality issues. By using a novel sol-gel procedure that provides both good quality surface passivation and high NC filling factors (> 15%), we fabricate PbSe NC/sol-gel nanocomposites that produce ASE, which is tunable via NC size, in the near-IR. This finding indicates the feasibility of NC-based amplifiers and lasers tunable in the near-IR range and, in particular, in the range of telecommunication windows.