Post-implant dosimetry for permanent prostate brachytherapy is typically performed using computed tomography (CT) images, for which the clear visualization of soft tissue structures is problematic. Registration of CT and magnetic resonance (MR) image volumes can improve the definition of all structures of interest (soft tissues, bones, and seeds) in the joint image set. In the present paper, we describe a novel two-stage rigid-body registration algorithm that consists of (1) parallelization of straight lines fit to image features running primarily in the superior-inferior (Z) direction, followed by (2) normalized mutual information registration. The first stage serves to fix rotation angles about the anterior-posterior (Y) and left-right (X) directions, and the second stage determines the remaining Z-axis rotation angle and the X, Y, Z translation values. The new algorithm was applied to CT and 1.5T MR (T2-weighted and balanced fast-field echo sequences) axial image sets for three patients acquired four weeks after prostate brachytherapy using 125I seeds. Image features used for the stage 1 parallelization were seed trains in CT and needle tracks and seed voids in MR. Simulated datasets were also created to further investigate algorithm performance. Clinical image volumes were successfully registered using the two-stage approach to within a root-mean-squares (RMS) distance of <1.5 mm, provided that some pubic bone and anterior rectum were included in the registration volume of interest and that no motion artifact was apparent. This level of accuracy is comparable to that obtained for the same clinical datasets using the Procrustes algorithm. Unlike Procrustes, the new algorithm can be almost fully automated, and hence we conclude that its further development for application in post-implant dosimetry is warranted.