Physical activity guidelines for cancer survivors issued by the American Cancer Society and the American College of Sports Medicine emphasize the essential role of a health care provider (HCP) in counseling cancer survivors to achieve healthier lifestyles. However, research has not established whether HCP's recommendations to engage in physical activity are associated with increased physical activity levels of cancer survivors. The study examines this potential association using the 2005 and 2010 National Health Interview Survey data. The final analytic sample consisted of 3320 cancer survivors and 38,955 adults without cancer who reported seeing or talking to a HCP and if or not they had received a physical activity recommendation in the prior year. Consistent with the aforementioned guidelines, physical activity levels were categorized as inactive, insufficiently active, and sufficiently active (i.e., meeting guidelines). Average adjusted predictions and marginal effects were estimated from generalized ordered logit models. Multivariable regressions controlled for socio-demographic and health-related characteristics and survey year. On average, receipt of a HCP's physical activity recommendation was associated with a lower adjusted prevalence of inactivity by 8.3 percentage points and a higher adjusted prevalence of insufficient and sufficient activity by 4.6 and 3.7 percentage points, respectively, regardless of cancer diagnosis (P's < 0.05). A HCP's recommendation is associated with higher levels of leisure-time aerobic physical activity among cancer survivors and adults without cancer. The communication between cancer survivors and their HCPs may act as a ‘window’ of opportunity to increase physical activity levels among the U.S. cancer survivors.