Cowden syndrome (CS) and Bannayan-Riley-Ruvalcaba syndrome are allelic, defined by germline PTEN mutations, and collectively referred to as PTEN hamartoma tumor syndrome. To date, there are no existing criteria based on large prospective patient cohorts to select patients for PTEN mutation testing. To address these issues, we conducted a multicenter prospective study in which 3042 probands satisfying relaxed CS clinical criteria were accrued. PTEN mutation scanning, including promoter and large deletion analysis, was performed for all subjects. Pathogenic mutations were identified in 290 individuals (9.5%). To evaluate clinical phenotype and PTEN genotype against protein expression, we performed immunoblotting (PTEN, P-AKT1, P-MAPK1/2) for a patient subset (n = 423). In order to obtain an individualized estimation of pretest probability of germline PTEN mutation, we developed an optimized clinical practice model to identify adult and pediatric patients. For adults, a semiquantitative score—the Cleveland Clinic (CC) score—resulted in a well-calibrated estimation of pretest probability of PTEN status. Overall, decreased PTEN protein expression correlated with PTEN mutation status; decreasing PTEN protein expression correlated with increasing CC score (p < 0.001), but not with the National Comprehensive Cancer Network (NCCN) criteria (p = 0.11). For pediatric patients, we identified highly sensitive criteria to guide PTEN mutation testing, with phenotypic features distinct from the adult setting. Our model improved sensitivity and positive predictive value for germline PTEN mutation relative to the NCCN 2010 criteria in both cohorts. We present the first evidence-based clinical practice model to select patients for genetics referral and PTEN mutation testing, further supported biologically by protein correlation.