This paper describes a new three-dimensional (3D) ultrasound robotic prostate brachytherapy system. It uses a stationary 3D ultrasound probe rigidly fixed to a robotic needle insertion mechanism. The novelty of the system is its ability to track prostate motion intra-operatively to allow the dose planning and needle trajectories or depths to be adapted to take into account these motions. Prostate tracking is done using a fast 3D ultrasound registration algorithm previously validated for biopsy guidance. The 7 degree of freedom robot and ultrasound probe are calibrated together with an accuracy of 0.9mm, allowing the needles to be precisely inserted to the seed targets chosen in the reference ultrasound image. Experiments were conducted on mobile deformable synthetic prostate phantoms, using a prototype laboratory system. Results showed that, with prostate motions of up to 7mm, the system was able to reach the chosen targets with less than 2mm accuracy in the needle insertion direction. This measured accuracy included extrinsic measurement errors of up to 1.1mm. A preliminary cadaver feasibility study was also described, in preparation for more realistic experimentation of the system.