Fast, reliable and accurate PET image segmentation is essential in the delineation of volumes when PET images are used for radiation therapy treatment planning. The aim of this study was to investigate the performance on static and gated PET images of a 3D random walk image segmentation algorithm, which makes use of an automated seed selection method and an adaptive probability threshold (3DAARW). This segmentation algorithm was compared to the performance of a published 2D adaptive probability threshold random walk (2DAARW) and to 2D and 3D random walk algorithms (2DARW and 3DARW) which used a fixed probability threshold and the same automated seed selection methodology as the 3DAARW. Optimal segmentation parameters for all 4 segmentation methods were determined on 18F-FDG PET/CT images of the NEMA IEC phantom acquired with source-to-background ratios of 3:1, 6:1 and 9:1 in both static and respiratory motion induced (gated) conditions. Segmentation performance was assessed by calculating the Dice Coefficient with the ground truth CT. It was found that, under the conditions investigated, the 3DAARW performed best on the static images, whilst the 3DARW performed best on the gated images.