Peptidomimetic inhibitors of fibroblast activation protein (FAP) are regarded as promising tools for tumor targeting in vivo. Even though several peptidomimetic compounds with nanomolar potency have been described, broad chemical space for further modification remained unexplored. Therefore, we set to analyze the structure-activity relationship (SAR) of pseudopeptide compound series with α-ketoamide warheads in order to explore the contributions of the P1' and P2' moieties to the inhibitory potency. A series of novel inhibitors bearing varied P1' and/or P2' moieties was synthesized by combining a Passerini reaction-Amine Deprotection-Acyl Migration (PADAM) approach with peptide coupling and subsequent oxidation. The resulting compounds inhibited FAP and the related prolyl endopeptidase (PREP) with potencies in the nanomolar to sub-nanomolar range. The most potent FAP inhibitor IOCB22-AP446 (6d, IC50 = 89 pM) had about 36-fold higher inhibition potency than the most potent inhibitor published to date. The compounds were selective over FAP's closest homolog DPP-IV, were stable in human and mouse plasma and in mouse microsomes, and displayed minimal cytotoxicity in tissue cultures.