Purpose: To develop an improved nuclear halo dose model of a pencil beam algorithm (PBA) for dose calculation of proton beams in heterogeneous media. Methods: The proton PBA consisted of a central axis term and an off axis term. The central axis term was determined from a central axis depth dose of a proton beam in water and was scaled by the mass stopping power ratio to account for other materials. The off axis term was determined from Fermi‐Eyges scattering theory with material‐dependent scattering powers to calculate the spread of the proton beam in heterogeneous media. The nuclear halo dose arising from large angle and non‐elastic scatter was modeled using two terms: a Gaussian and a Cauchy‐Lorentz distribution. Depth‐dependent widths and amplitudes of each distribution were determined by fitting a simulated 1‐mm × 1‐mm pencil beam in water. The PBA was evaluated in approximately 30 test phantoms containing bone and/or air heterogeneities for 4 energies and 2 field sizes. Agreement between PBA and Monte Carlo simulations of the test conditions was quantified by computing the percentage of points within 2 percent dose difference or 1 mm distance to agreement. Results: With the improved nuclear halo model, PBA calculations showed better than of 97% of dose points within 2%/1 mm of MC distributions for all geometries examined. For phantoms containing laterally infinite heterogeneities, agreement between PBA and MC distributions was 100% at 2%/1mm. For phantoms containing laterally finite heterogeneities, agreement was at least 97%. The points failing were due to the central axis approximation of the PBA in regions not influenced by the nuclear halo model. Conclusions: The halo model developed in this work improves the agreement of the PBA with MC simulations in heterogeneous phantoms, particularly in low‐dose regions that can be important for scanned‐beam proton therapy. “This research was supported by contract W81XWH‐10‐1‐0005 awarded by The U.S. Army Research Acquisition Activity, 820 Chandler Street, Fort Detrick, MD 21702‐5014. This report does not necessarily reflect the position or policy of the Government, and no official endorsement should be inferred”.