Localization of prostate cancer recurrence, particularly in the bones, is a major challenge with standard of care imaging in patients with biochemical recurrence following curatively intended treatment. Gallium-68-labeled prostate specific membrane antigen positron emission tomography/computed tomography ((68)Ga-PSMA PET/CT) is a novel and promising method for imaging in prostate cancer. The present study reports two cases of patients with prostate cancer with biochemical recurrence, with evidence of bone metastases on (68)Ga-PSMA PET/CT images and low prostate specific antigen PSA levels (<2 ng/ml) and PSA doubling time >6 months. The bone metastases were verified by supplementary imaging with (18)F-sodium fluoride PET/CT and magnetic resonance imaging as well as biochemical responses to androgen deprivation therapy. Therefore, (68)Ga-PSMA PET/CT is promising for the restaging of patients with prostate cancer with biochemical recurrence, including patients with low PSA levels and low PSA kinetics.