Carriers of mismatch repair (MMR) gene mutations have a high lifetime risk for colorectal and endometrial cancers, as well as other malignancies. As mutation analysis to detect these patients is expensive and time-consuming, clinical criteria and tumor-tissue analysis are widely used as pre-screening methods. The aim of our study was to evaluate the performance of commonly applied clinical criteria (the Amsterdam I and II Criteria, and the original and revised Bethesda Guidelines) and the results of tumor-tissue analysis in predicting MMR gene mutations. We analyzed 3,671 families from the German HNPCC Registry and divided them into nine mutually exclusive groups with different clinical criteria. A total of 680 families (18.5%) were found to have a pathogenic MMR gene mutation. Among all 1,284 families with microsatellite instability-high (MSI-H) colorectal cancer, the overall mutation detection rate was 53.0%. Mutation frequencies and their distribution between the four MMR genes differed significantly between clinical groups (p < 0.001). The highest frequencies were found in families fulfilling the Amsterdam Criteria (46.4%). Families with loss of MSH2 expression had higher mutation detection rates (69.5%) than families with loss of MLH1 expression (43.1%). MMR mutations were found significantly more often in families with at least one MSI-H small-bowel cancer (p < 0.001). No MMR mutations were found among patients under 40-years-old with only colorectal adenoma. Familial clustering of Lynch syndrome-related tumors, early age of onset, and familial occurrence of small-bowel cancer were clinically relevant predictors for Lynch syndrome.