The HIV epidemic is a health crisis in rural African American communities in the Southeast United States; however, to date little attention has been paid to community-academic collaborations to address HIV in these communities. Interventions that use a community-based participatory research (CBPR) approach to address individual, social, and physical environmental factors have great potential for improving community health. Project GRACE (Growing, Reaching, Advocating for Change and Empowerment) uses a CBPR approach to develop culturally sensitive, feasible, and sustainable interventions to prevent the spread of HIV in rural African American communities. This article describes a staged approach to community-academic partnership: initial mobilization, establishment of organizational structure, capacity building for action, and planning for action. Strategies for engaging rural community members at each stage are discussed; challenges faced and lessons learned are also described. Careful attention to partnership development has resulted in a collaborative approach that has mutually benefited both the academic and community partners.