We have identified two synthetic oligonucleotides (aptamers) that bind to prostate cancer cells,with low nanomolar affinity, via the extracellular portion of the prostate-specificmembrane antigen (PSMA). These two specific aptamers were selected from an initial 40mer library of ∼6 × 10¹⁴ random-sequence RNA molecules for their ability to bind to a recombinant protein representing the extracellular 706 amino acids of PSMA, termed xPSM. Six rounds of in vitro selection were performed, enriching for xPSM binding as monitored by aptamer inhibition of xPSM N-acetyl-α-linked acid dipeptidase (NAALADase) enzymatic activity. By round six, 95% of the aptamer pool consisted of just two sequences. These two aptamers, termed xPSM-A9 and xPSM-A10, were cloned and found to be unique, sharing no consensus sequences. The affinity of each aptamer for PSMA was quantitated by its ability to inhibit NAALADase activity. Aptamer xPSM-A9 inhibits PSMA noncompetitively with an average K_i of 2.1 nm, whereas aptamer xPSM-A10 inhibits competitively with an average K_i of 11.9 nm. Distinct modes of inhibition suggest that each aptamer identifies a unique extracellular epitope of xPSM. One aptamer was truncated from 23.4 kDa to 18.5 kDa and specifically binds LNCaP human prostate cancer cells expressing PSMA but not PSMA-devoid PC-3 human prostate cancer cells. These are the first reported RNA aptamers selected to bind a tumor-associated membrane antigen and the first application of RNA aptamers to a prostate specific cell marker. These aptamers may be used clinically as NAALADase inhibitors or be modified to carry imaging agents and therapeutic agents directed to prostate cancer cells.