GATE (Geant4 Application for Emission Tomography) is a widespread, well validated and very versatile application for Monte Carlo simulations in emission tomography. Its computational performance is poor, especially for voxelized phantoms, due to the use of a very general particle tracking algorithm. In this work, two methods are proposed to reduce the time spent on particle tracking in the phantom: 1) a newly introduced regular navigation algorithm of Geant4 and 2) fictitious photon tracking (also known asWoodcock tracking). Accuracy and execution time gain are investigated using a realistic phantom based upon a head and neck scan. The execution time could be reduced by a factor of ten when the voxel size of the attenuation phantom was 3.52 × 3.52 × 3.26mm3 or even by a factor of 24 when the voxel size was 1.17 × 1.17 × 1.09mm3 (voxel size of the underlying CT image used for the attenuation map).