A 3D model of abdominal aortic aneurysm (AAA) can provide useful anatomical information for clinical management and simulation. Thin-slice contiguous computed tomographic (CT) angiography is the best source of medical images for construction of 3D models, which requires segmentation of AAA in the images. Existing methods for segmentation of AAA rely on either manual process or 2D segmentation in each 2D CT slide. However, a traditional manual segmentation is a time consuming process which is not practical for routine use. The construction of a 3D model from 2D segmentation of each CT slice is not a fully satisfactory solution due to rough contours that can occur because of lack of constraints among segmented slices, as well as missed segmentation slices. To overcome such challenges, this paper proposes the 3D segmentation of AAA using the concept of variable neighborhood search by iteratively alternating between two different segmentation techniques in the two different 3D search spaces of voxel intensity and voxel gradient. The segmentation output of each method is used as the initial contour to the other method in each iteration. By alternating between search spaces, the technique can escape local minima that naturally occur in each search space. Also, the 3D search spaces provide more constraints across CT slices, when compared with the 2D search spaces in individual CT slices. The proposed method is evaluated with 10 easy and 10 difficult cases of AAA. The results show that the proposed 3D segmentation technique achieves the outstanding segmentation accuracy with an average dice similarity value (DSC) of 91.88%, when compared to the other methods using the same dataset, which are the 2D proposed method, classical graph cut, distance regularized level set evolution, and registration based geometric active contour with the DSCs of 87.57 ± 4.52%, 72.47 ± 8.11%, 58.50 ± 8.86% and 76.21 ± 10.49%, respectively.