The sharp lateral penumbra and the rapid fall-off of dose at the end of range of a proton beam are among the major advantages of proton radiation therapy. These beam characteristics depend on the position and characteristics of upstream beam-modifying devices such as apertures and compensating boluses. The extent of separation, if any, between these beam-modifying devices and the patient is particularly critical in this respect. We have developed a pencil beam algorithm for proton dose calculations which takes accurate account of the effects of materials upstream of the patient and of the air gap between them and the patient. The model includes a new approach to picking the locations of the pencil beams so as to more accurately model the penumbra and to more effectively account for the multiple-scattering effects of the media around the point of interest. We also present a faster broad-beam version of the algorithm which gives a reasonably accurate penumbra. Predictions of the algorithm and results from experiments performed in a large-field proton beam are presented. In general the algorithm agrees well with the measurements.