The goal of this study was to describe HIV risk behaviors, perceptions, testing, and prevention exposure among urban American Indians and Alaska Natives (AI/AN). Interviewers administered a questionnaire to participants recruited through anonymous peer-referral sampling. Chi-square tests and multiple logistic regression were used to compare HIV testing by perception of risk and risk behavior status. Of 218 respondents with seronegative or unknown HIV status, 156 (72%, 95% confidence interval [CI]: 66-78%) reported some HIV risk behavior: 57 (26%, 95% CI: 20-32%) high-risk behavior, and 99 (45%, 95% CI: 39-52%), potentially high-risk. Among respondents reporting high-risk behavior, 44% rated themselves at no or low risk for HIV infection. Overall, 180 respondents (83%, 95% CI: 78-88%) had ever received an HIV test, 79 (36%, 95% CI: 31-57%) in the past year. HIV risk behaviors and perception of risk were independently associated with recent HIV testing after adjustment for gender, income, and homelessness (odds ratio [OR] = 3.6; 95% CI: 1.5-9.0 for high-risk behavior vs. no reported risk behavior, and OR: 3.2; 95% CI: 1.3-7.6, for high vs. no perceived risk). Addressing inaccurate perception of risk may be a key to improving uptake of HIV testing among high-risk urban AI/AN.