Targeting Prostate Specific Membrane Antigen (PSMA) has proven highly useful and beneficial for prostate cancer (PCa) theranostics. However, patients with advanced metastatic castration-resistant prostate cancer (mCRPC) lack optimal PSMA expression resulting in poor specificity. To address this limitation, combination targeting is gaining popularity by synergistically boosting the theranostic efficacy. Herein, we thoroughly reviewed the most recent development of drug formulation for PCa theranostics by targeting both PSMA and Fibroblast Activation Protein (FAP). FAP is known to overexpress in cancer-associated fibroblasts (CAFs) within the tumor microenvironment (TME). It has been extensively studied as an effective target for the identification and treatment of a variety of cancer phenotypes. Along with the advantages and current updates on combination targeting of PSMA and FAP, this Review thoroughly discussed the expression patterns of PSMA and FAP in various cancer phenotypes, as well as their role in tumor growth, invasion, and metastasis, which is of great interest in the design and development of prostate cancer theranostics.