Mammography is the primary method used for breast cancer screening. However, compliance with recommended screening practices is still below acceptable levels. This study examined the cost-effectiveness of five combinations of physician recommendation and telephone or in-person individualized counseling strategies for increasing compliance with mammography. There were 808 participants who were randomly assigned to one of six groups. A logistic regression model with compliance as the dependent variable and group as the independent variable was used to test for significant differences and a ratio of cost to improvement in mammogram compliance evaluated the cost-effectiveness. Three of the interventions (in-person, telephone plus letter, and in-person plus letter) had significantly better compliance rates compared with the control, physician letter, or telephone alone. However, when considering costs, only one emerged as the superior strategy. The cost-effectiveness ratios for the five interventions show that telephone-plus-letter is the most cost-effective strategy, achieving a 35.6% mammography compliance at a marginal cost of $0.78 per 1% increase in women screened. A tailored phone prompt and physician reminder is an effective and economical intervention to increase mammography. Future research should confirm this finding and address its applicability to practice.