Context: Regular screenings are important for reducing cancer morbidity and mortality. There are several barriers to receiving timely cancer screening, including overweight/obesity. No study has examined the relationship between overweight/obesity and cancer screening among American Indian/Alaska Natives (AI/ANs). Purpose: To describe the prevalence of fecal occult blood testing (FOBT) and prostate-specific antigen (PSA) testing among AI/AN men within the past year by age and rurality, and determine if body mass index (BMI) is associated with screening. Methods: A national cross-sectional survey was administered face-to-face to 2,447 AI/AN men at least 55 years of age in 2004-2005. Participants were asked when they last had FOBT and PSA testing. BMI was derived from self-reported height and weight, and rurality of residence was defined by rural-urban commuting area codes. We assessed the association of cancer screening and BMI with logistic regression models, adjusting for demographic and health factors. Findings: Prevalence of up-to-date FOBT and PSA testing were 23% and 40%, respectively. Older men were more likely than younger men to have FOBT and PSA testing. BMI was not associated with receipt of FOBT or PSA testing. Conclusions: This is the first study to examine obesity and health care in AI/ANs. As in other populations, FOBT and PSA testing were suboptimal. Screening was not associated with BMI. Studies of AI/AN men are needed to understand the barriers to receiving timely screenings for prostate and colorectal cancer.