Purpose: Studies have shown that women who engage in high levels of physical activity have higher rates of cancer screening, including Papanicalaou (Pap) tests. Because American Indian (AI) women are at high risk for cervical cancer morbidity and mortality, we examined Pap screening prevalence and assessed whether physical activity was associated with screening adherence among AI women from 2 culturally distinct regions in the Northern Plains and the Southwest. Methods: A total of 1,979 AI women at least 18 years of age participating in a cross-sectional cohort study reported whether they received a Pap test within the previous 3 years. Physical activity level was expressed as total metabolic equivalent (MET) scores and grouped into quartiles. We used binary logistic regression to model the association of Pap testing and MET quartile, adjusting for demographic and health factors. Findings: Overall, 60% of women received a Pap test within the previous 3 years. After controlling for covariates, increased physical activity was associated with higher odds of Pap screening (OR = 1.1 per increase in MET quartile; 95% CI = 1.1, 1.2). Conclusions: This is the first study to examine physical activity patterns and receipt of cancer screening in AIs. While recent Pap testing was more common among physically active AI women, prevalence was still quite low in all subgroups. Efforts are needed to increase awareness of the importance of cervical cancer screening among AI women.