We present the results of a detailed study of the accretion of planetesimals by a growing proto-Jupiter in the core-accretion model. Our study was motivated by the fact that the initial conditions in the original calculations of planetesimal accretion and its subsequent revisions were ad hoc and not consistent with the natural evolution of the system. These models did not include certain effects such as the gravitational force of the Sun and the perturbation of a growing proto-Saturn, as well. We have developed a new code that accurately models the interaction of planetesimals with the envelope of a growing giant planet in a self-consistent manner. Our code takes into account the effect of the central star and a second (growing) giant planet, and includes all physical processes involved in the interaction of a planetesimal with the proto-giant-planet envelop. It calculates the trajectories of planetesimals outside and inside the envelope self-consistently by combining detailed four-body integrations with gas drag. Results point to several new findings. For instance, we find that in a Sun-Jupiter-Saturn system, significant amount of solid mass is accreted by proto-Jupiter before the onset of rapid gas accretion, and approximately 10 Earth-masses is accreted simultaneously during this phase. We also find that mass accretion remains small (appriximately 0.3 Earth-masses) for about 1.5 Myr after this time. This late accretion, together with a rapid infall of gas, could lead to a mixing of accreted material throughout the outer regions, which may explain the enhancement of high-Z material in Jupiter’s envelope. Results also demonstrate that if Saturn’s perturbation is ignored, planetesimal encounters with the protoplanetary envelope become so fast that in most cases, ram pressure breaks them up. As a result, the accretion rate becomes largely independent of the planetesimals’ size and composition. However, when Saturn’s perturbation is included, the capture rate increases early on, and in that case, because the envelope is less massive, more planetesimals can penetrate to the core. We present details of our calculations and discuss the implications of the results for the metallicity of Jupiter and Saturn, and the density of extrasolar giant planets.