In prostate brachytherapy, transrectal ultrasound (TRUS) is used to visualize the anatomy, while implanted seeds can be seen in C-arm fluoroscopy. Intra-operative dosimetry optimization requires reconstruction of the implanted seeds from multiple C-arm fluoroscopy images, which in turn requires estimation of the C-arm poses. We estimate the pose of the C-arm by two-stage registration between the 2D fluoroscopy images to a 3D TRUS volume. As single-view 2D/3D registration tends to yield depth error, we first estimate the depth from multiple 2D fluoro images and input this to a single-view 2D/3D registration. A commercial phantom was implanted with seeds and imaged with TRUS and CT. Ground-truth registration was established between the two by radiographic fiducials. Synthetic ground-truth fluoro images were created from the CT volume and registered to the 3D TRUS. The average rotation and translation errors were 1.0 degrees (STD = 2.3 degrees) and 0.7 mm (STD = 1.9 mm), respectively. In data from a human patient, the average rotation and lateral translation errors were 0.6 degrees (STD = 3.0 degrees) and 1.5 mm (STD = 2.8 mm), respectively, relative to the ground-truth established by a radiographic fiducial. Fully automated image-based C-arm pose estimation was demonstrated in prostate brachytherapy. Accuracy and robustness was excellent on phantom. Early result in human patient data appears clinically adequate.