Telephone-delivered interventions do not require frequent clinic visits, literacy, or costly technology and thus may represent promising approaches to promoting physical activity in the Deep South, a largely rural U.S. region, with generally lower physical activity, income, and education levels. Building on past Interactive Voice Response (IVR) system-based HIV studies and extensive formative research (11 focus groups on physical activity intervention needs/preferences in the Deep South), the resulting IVR-supported physical activity intervention is now being tested in a randomized controlled trial with a waitlist control. The sample (n = 63) includes mostly obese (Mean BMI = 30.1) adults (Mean age = 43 years) in Birmingham, AL. Both genders (55.6% male) and African Americans (58.7%) are well-represented. Most participants reported at least some college (92%), full time employment (63.5%), and household income <$50,000 per year (61.9%). Baseline physical activity (Mean = 39.6 min/week, SD = 56.4), self-efficacy, self-regulation, and social support were low. However, high physical activity enjoyment and outcome expectations bode well. Self-report physical activity was associated with physical activity enjoyment (r = 0.36) and social support (friends r = 0.25, p's < 0.05) at baseline. Consequently, these may be important variables to emphasize in our program. Depression and anxiety were negatively correlated with some early indicators of behavior change (e.g., physical activity self-regulation; r's = -0.43 and −0.46, respectively, p's < 0.01) and thus may require additional attention. Such technology-supported strategies have great potential to reach underserved populations and address physical activity-related health disparities in this region.