Accurate localization of the prostate and its surrounding tissue is essential in the treatment of prostate cancer. This paper presents a novel approach to fully automatically segment the prostate, including its seminal vesicles, within a few minutes of a magnetic resonance (MR) scan acquired without an endorectal coil. Such MR images are important in external beam radiation therapy, where using an endorectal coil is highly undesirable. The segmentation is obtained using a deformable model that is trained on-the-fly so that it is specific to the patient's scan. This case specific deformable model consists of a patient specific initialized triangulated surface and image feature model that are trained during its initialization. The image feature model is used to deform the initialized surface by template matching image features (via normalized cross-correlation) to the features of the scan. The resulting deformations are regularized over the surface via well established simple surface smoothing algorithms, which is then made anatomically valid via an optimized shape model. Mean and median Dice's similarity coefficients (DSCs) of 0.85 and 0.87 were achieved when segmenting 3T MR clinical scans of 50 patients. The median DSC result was equal to the inter-rater DSC and had a mean absolute surface error of 1.85 mm. The approach is showed to perform well near the apex and seminal vesicles of the prostate.