We here aim to provide a comprehensive and critical review of the literature concerning the clinical applications of positron emission tomography/computed tomography (PET/CT) with radiolabeled choline in patients with prostate cancer (PCa). We will initially briefly summarize the historical context that brought to the synthesis of [C]choline, which occurred exactly 20 years ago. We have arbitrarily grouped the clinical studies in three different periods, according to the year in which they were published and according to their relation with their applications in urology, radiotherapy and oncology. Studies at initial staging and, more extensively, studies in patients with biochemical failure, as well as factors predicting positive PET/CT will be reviewed. The capability of PET/CT with radiolabeled choline to provide prognostic information on PCa-specific survival will also be examined. The last sections will be devoted to the use of radiolabeled choline for monitoring the response to androgen deprivation therapy, radiotherapy, and chemotherapy. The accuracy and the limits of the technique will be discussed according to the information available from standard validation processes, including biopsy or histology. The clinical impact of the technique will be discussed on the basis of changes induced in the management of patients and in the evaluation of the response to therapy. Current indications to PET/CT, as officially endorsed by guidelines, or as routinely performed in the clinical practice will be illustrated. Emphasis will be made on methodological factors that might have influenced the results of the studies or their interpretation. Finally, we will briefly highlight the potential role of positron emission tomography/magnetic resonance and of new radiotracers for PCa imaging.