To investigate the effectiveness of a TTM-based motivational counselling approach by trained practice nurses to promote physical activity of low back pain patients in a German primary care setting. Data were collected in a cluster-randomized controlled trial with three study arms via questionnaires and patient interviews at baseline and after 6 and 12 months. We analysed total physical activity and self-efficacy by using random effect models to allow for clustering. A total of 1378 low back pain patients, many with acute symptoms, were included in the study. Nearly 40% of all patients reported sufficient physical activity at baseline. While there were significant improvements in patients physical activity behaviour in all study arms, there was no evidence for an intervention effect. The outcome may be explained by insufficient performance of the practice nurses, implementation barriers caused by the German health care system and the heterogenous sample. Given the objective to incorporate practice nurses into patient education, there is a need for a better basic training of the nurses and for a change towards an organizational structure that facilitates patient-nurse communication. Counselling for low back pain patients has to consider more specificated aims for different subgroups.