Although CDC guidelines call for universal, “opt-out” HIV testing, barriers to testing continue to exist throughout the United States, with the rural South particularly vulnerable to both HIV infection and decreased awareness of status. Therefore, the objectives of this study were to evaluate uptake of “opt-out” HIV testing and barriers to testing within the primary care setting in the South. A concurrent triangulation design guided the collection of quantitative data from patients (N = 250) and qualitative data from providers (N = 10) across three primary health clinics in Alabama. We found that 30% of patients had never been tested for HIV, with the highest ranked barrier among patients being perceived costs, access to specialty care, and not feeling at risk. Significant differences existed in perceived barriers between patients and providers. Increased provider-patient engagement and the routine implementation of “opt-out” HIV testing would effectively reveal and mitigate barriers to testing, thus, increasing awareness of status.