In the past two decades, extensive efforts have been made to develop agents targeting prostate-specific membrane antigen (PSMA) for prostate cancer imaging and therapy. To date, represented by two recent approvals of [Ga]Ga-PSMA-11 and [F]F-DCFPyL by the United States Food and Drug Administration (US-FDA) for positron emission tomography (PET) imaging to identify suspected metastases or recurrence in patients with prostate cancer, PSMA-targeting imaging and theranostic agents derived from small molecule PSMA inhibitors have advanced to clinical practice and trials of prostate cancer. The focus of current development of new PSMA-targeting agents has thus shifted to the improvement of in vivo pharmacokinetics and higher specific binding affinity with the aims to further increase the detection sensitivity and specificity and minimize the toxicity to non-target tissues, particularly the kidneys. The main strategies involve systematic chemical modifications of the linkage between the targeting moiety and imaging/therapy payloads. In addition to a summary of the development history of PSMA-targeting agents, this review provides an overview of current advances and future promise of PSMA-targeted imaging and theranostics with focuses on the structural determinants of the chemical modification towards the next generation of PSMA-targeting agents.