Background: Accurate surveillance data on physical activity prevalence is important for U.S. states and territories as they develop programs and interventions to increase physical activity participation. Methods: Using 2007 data from the Behavioral Risk Factor Surveillance System, we estimated the percentage of U.S. adults in each U.S. state and territory who met minimum aerobic activity criteria using the 2008 Physical Activity Guidelines for Americans (2008 Guidelines) and the Healthy People 2010 criteria for physical activity. SUDAAN was used to calculate prevalence estimates and 95% confidence intervals. Results: The estimated prevalence of recommended aerobic activity in U.S. states and territories ranged from 44.5% to 73.3% according to 2008 Guidelines and from 30.8% to 60.0% according to Healthy People 2010 criteria. Absolute percent differences in prevalence among U.S. states and territories ranged from 11.7% to 19.1%, and relative percent differences ranged from 20.8% to 44.6%. Conclusions: In all U.S. states and territories, a larger proportion of U.S. adults met minimum aerobic activity criteria in the 2008 Guidelines than met corresponding criteria in Healthy People 2010. This difference, however, does not reflect an actual change in the amount of aerobic activity, but a change to the criteria for meeting 2008 Guidelines.