We propose a novel fiducial-free approach for the registration of C-arm fluoroscopy to 3D ultrasound images of prostate brachytherapy implants to enable dosimetry. The approach involves the reliable detection of a subset of radioactive seeds from 3D ultrasound, and the use of needle tracks in both ultrasound and fluoroscopy for registration. Seed detection in ultrasound is achieved through template matching in 3D radio frequency ultrasound signals, followed by thresholding and spatial filtering. The resulting subset of seeds is registered to the complete reconstruction of the brachytherapy implant from multiple C-arm fluoroscopy views. To compensate for the deformation caused by the ultrasound probe, simulated warping is applied to the seed cloud from fluoroscopy. The magnitude of the applied warping is optimized within the registration process. The registration is performed in two stages. First, the needle track projections from fluoroscopy and ultrasound are matched. Only the seeds in the matched needles are then used as fiducials for point-based registration. We report results from a physical phantom with a realistic implant (average postregistration seed distance of 1.6±1.2 mm) and from five clinical patient datasets (average error: 2.8±1.5 mm over 128 detected seeds). We conclude that it is feasible to use RF ultrasound data, template matching, and spatial filtering to detect a reliable subset of brachytherapy seeds from ultrasound to enable registration to fluoroscopy for dosimetry.