Background: General practitioners (GPs) cite time as a barrier to physical activity counseling. An alternative for time-poor GPs in Australia is the referral of insufficiently active patients to exercise physiologists (EPs). As data on the predictors of adherence to physical activity counseling interventions are limited, this study aimed to identify the sociodemographic, medical, health, and psychological characteristics of insufficiently active primary care patients who adhered to a physical activity counseling intervention delivered by EPs. Methods: This secondary analysis of data from the NewCOACH randomized trial used logistic regression to identify predictors of adherence, defined as patient participation in at least four of the five physical activity counseling sessions. EPs provided information about the number of sessions, while other potential predictors were obtained from the self-administered baseline questionnaire and medical summary sheets provided by the GPs. Results: Of the 132 patients referred to an EP, 102 (77%) were adherent: 91 (69%) and eleven (8.3%) participated in all, or all but one, of the sessions, respectively. Of the remainder, seven (5.3%) patients participated in three sessions, seven (5.3%) participated in two sessions, five (3.8%) participated in one session, and eleven (8.3%) did not participate in any session. The odds of being adherent were 5.84 (95% CI 1.46–23.4, P≤0.05) times higher among retired participants than in those who were not in paid employment. The odds of being adherent 1) increased as the positive outcome expectation score increased (OR 1.89, 95% CI 1.12–3.18, P≤0.05) and 2) decreased as the duration (days) between referral and the initial counseling session increased (OR 0.95, 95% CI 0.92–0.98, P<0.01). Conclusion: More than three quarters of the patients participated in all, or all but one, of the sessions. Being retired, positive outcome expectations, and having a shorter wait between referral and the initial appointment predicted adherence.