This primary care-based study aimed to evaluate the efficacy and feasibility of a 24-week intervention on physical activity and physical fitness in a group of community-dwelling older adults. Secondary aims were to determine the effect of the intervention on self-efficacy and barriers to physical activity. Intervention participants (n=36) received an exercise prescription based on physical fitness test results and personal choice. Comparison participants (n=36) received a nutrition intervention. Both groups received 10 follow-up telephone calls. Repeated measures ANOVA analyses showed no direct effects of the intervention on the primary outcomes of physical activity or physical fitness in the intervention group (p>0.05). Secondary analyses with ANCOVA that included potential moderating variables of age, gender, income, BMI, and support for physical activity showed that the intervention group significantly increased frequency of all physical activity (F=3.50, p<0.05) as well as the fitness outcomes of lower body strength (F=3.63, p<0.05) and aerobic endurance (F=4.03, p<0.05). This is one of the first studies to evaluate the use of fitness measures to increase physical activity and fitness in the primary care setting. The intervention improved some aspects of physical activity and fitness for selected participants.