A 72-year-old man with a history of T1cN0M0 prostate adenocarcinoma and rising prostate-specific antigen underwent a fluciclovine PET/CT scan that showed high uptake in several para-aortic nodes, suspicious for prostate cancer. A right upper lobe single pulmonary nodule (SPN), demonstrated only mild uptake, which raised the suspicion for a lung primary. Subsequent FDG PET/CT showed high uptake in the SPN, revealing poorly differentiated adenocarcinoma at biopsy, but with no abnormal uptake in the para-aortic nodes. This case highlights the complementary potential of fluciclovine and FDG PET in patients with a history of prostate cancer biochemical recurrence and SPN.