This paper presents a fast, six degrees of freedom registration technique to accurately locate the position and orientation of medical volumes (obtained from CT/MRI scans for the same patient) with respect to each other. The main contribution of this work is the use of a novel surface registration technique followed by a volume registration approach. The advantage of this combination is to have an accurate alignment and to reduce the time needed for registration. The surface registration uses a new surface representation scheme that captures the curvature information and codes it into 2-D images. Matching these images enables the recovery of the transformation parameters. For the multi-modal volume registration, the maximization of Mutual Information (MI) is used as a matching criterion and is enhanced by a new genetic based search technique. The results demonstrate that the new two-stage registration technique presented in this paper is robust in terms of speed and accuracy and allows for completely automatic registration of multimodality medical volumes.