Transrectal ultrasound (TRUS) image-guidance is crucial in monitoring prostate cancer by enabling precise lesion targeting for biopsy and radiotherapy. Image-guided navigation can be further improved by manually overlaying a 3D preoperative MRI scan to benefit from its superior contrast and resolution. Here we propose to automate this procedure, which we formulate as MRI-TRUS 3D rigid registration. However, this task faces three challenges: the large domain gap between MRI and TRUS; the relative spherical symmetry of the prostate that complicates rotation estimation; the potential large misalignments due to the wide range of ultrasound probe orientations relative to the MR coordinate frame. Here we present MUReg, a new pipeline for MRI-TRUS rigid registration. First, we initialize translations by aligning the prostate centers of mass derived from segmentations. Then, we regress rotations with an attention-based CNN that takes segmentations as inputs (to eliminate the domain gap) and that is trained with a novel loss penalizing displacement errors to alleviate the symmetry issue. Finally, we enhance the robustness of these initial predictions by using an iterative closest point algorithm. Overall, MUReg significantly outperforms state-of-the-art optimization and deep learning methods on four different metrics.