Objectives: We sought to determine the characteristics of women eligible for a high-yield screening mammography program in Oman. Methods: We conducted a retrospective review of women who underwent breast cancer screening at the Oman Cancer Association from 22 December 2009 to 6 February 2011. Women with a Breast Imaging Reporting and Data System (BI-RADS) score of 4–5 were compared with those with a score of 1–3 based on well-known breast cancer risk factors using the case-control approach analysis. Results: A BI-RADS score of 4–5 was found in 16.2% of women screened for breast cancer. A higher likelihood of a BI-RADS score of 4 or 5 was observed among women who did not breastfeed (odds ratio (OR) = 2.564; 95% confidence interval (CI): 1.690, 3.890), had their first pregnancy at an older age (OR = 1.062; 95% CI: 1.041, 1.083), used oral contraceptives (OR = 1.397; 95% CI: 1.008, 1.938), and those who reported a positive family history of malignancies (OR = 1.633; 95% CI: 1.285, 2.076). A BI-RADS score of 4 or 5 was significantly less likely in women with a higher number of full-term pregnancies (OR = 0.919; 95% CI: 0.890, 0.948). BI-RADS 4–5 were independently predicted in women with a lower number of full-term pregnancies, did not breastfeed, used oral contraceptives, and who had a positive family history of malignancies. These variables explained 84.0% of the variation in mammogram results. Conclusions: In the absence of a national screening program for breast cancer, the high-risk approach for screening should be considered. Women with the above characteristics should be identified and motivated to seek mammogram regularly to warrant a better outcome.