Background: In adults, as little as 10 minutes of moderate physical activity (PA) three times a day can help prevent non-communicable diseases and prolong life expectancy. The aim of the study was to evaluate the process and impact of scaling up a complex intervention (PAFES) implemented in Catalonia, aimed to increase the proportion of adults complying with PA recommendations (especially those with cardiovascular risk factors). Methods: The intervention, piloted in 2005, had three elements: 1) establishing clinical guidelines for PA; 2) identifying local PA resources; 3) PA screening and advice in primary health care (PHC) settings, based on stage of change. Central and local level implementation activities included training, support to municipalities, dissemination through a web page, and promotion of World Physical Activity Day (WPAD). Evaluation followed the RE-AIM framework (Reach, Effectiveness, Adoption, Implementation, Maintenance), identifying 3-6 variables for annual evaluation of each dimension. These included coverage of PA screening and advice and individuals with access to a healthy exercise route (Reach), increased PA level between 2006 and 2010-15 (Effectiveness), PAFES adoption by PHC centres and municipalities (Adoption), process evaluation data (Implementation), and cost (Maintenance). Results: PHC screening coverage increased from 14.4% (2008) to 69.6% (2015) and advice coverage from 8.3% (2012) to 35.6% (2015). In 2015, 82.5% patients had access to a "healthy route" (Reach). The proportion of patients with at least one cardiovascular risk factor who were "sufficiently active" increased from 2006 to 2010-2013 (Effectiveness). By 2015, PAFES was applied by all PHC teams, 8.3% municipalities and 22.7% PHC centres had organized WPAD events (Adoption). The Plan showed good penetration in all health regions by 2013, with relatively low use of resources and estimated cost (Implementation). By 2013 the Plan was embedded within the health system (Maintenance). Conclusions: In the first application of the RE-AIM framework to evaluate the scaling-up of a PA plan, PAFES showed good results for most RE-AIM indicators. Changes in priority and investment in health promotion programs affect reach, adoption, and effectiveness. It is important to maintain support until programs are strongly embedded into the health system.