Although prostate carcinoma (PCa) is by far the most commonly diagnosed neoplasia in men, corresponding diagnostic and therapeutic modalities have limited efficacy at present. Anticalins comprise a novel class of binding proteins based on a non-immunoglobulin scaffold that can be engineered to specifically address molecular targets of interest. Here we report the selection and characterization of Anticalins that recognize human prostate-specific membrane antigen (PSMA), a membrane-tethered metallopeptidase constituting a disease-related target for imaging and therapy of PCa as well as solid malignancies in general. We used a randomized lipocalin library based on the human lipocalin 2 (Lcn2) scaffold together with phage display and ELISA screening to select PSMA-specific variants. Five Anticalin candidates from the original panning were expressed in Escherichia coli as soluble monomeric proteins, revealing affinities toward PSMA down to the low nanomolar range. Binding characteristics of the most promising candidate were further improved via affinity maturation by applying error-prone PCR followed by selection via phage display as well as bacterial surface display under more stringent conditions. In BIAcore measurements, the dissociation constant of the best Anticalin was determined as ∼500 pM, with a substantially improved dissociation rate compared with the first-generation candidate. Finally, immunofluorescence microscopy revealed specific staining of PSMA-positive tumor cell lines while flow cytometric analysis confirmed the ability of the selected Anticalins to detect PSMA on live cells. Taken together, Anticalins resulting from this study offer a viable alternative to antibody-based PSMA binders for biomedical applications, including in vivo imaging of PCa or neovasculature of solid tumors.