Background: Anxiety and depression are not always diagnosed and treated in primary care as has been recommended. A tailored implementation programme, which addresses key barriers for change by targeted interventions, may help to remedy this. Methods: The effectiveness of an individually tailored implementation programme, additional to standardised training and feedback on the recognition and treatment of patients with anxiety or depression in general practice, was examined in a cluster randomised controlled trial. Participants were 46 general practitioners (GPs) from 23 general practices (12 intervention, 11 control) and 444 patients aged 18 years or older (198 intervention, 246 control) who screened positive on the extended Kessler 10. In the control group, GPs received a 1-day training in guidelines for recognition and stepped treatment for anxiety and depression. Ten months after the training session, GPs received feedback on their performance over the preceding 6 months. In the intervention group, GPs received the same training and feedback as those in the control condition; in addition, they were offered support, tailored to perceived local barriers to change. The support was delivered in the format of peer group supervisions and personalised telephone consultations. Data were based on an audit of patient records and patient surveys at baseline and after 3 and 6 months. Results: The tailored implementation programme led to recognition of a higher proportion of patients presenting with anxiety and depression (42% versus 31%; odds ratio (OR) = 1.60; 95% CI: 1.01-2.53), more consultations after recognition (IRR = 1.78; 95% CI: 1.14-2.78) and did not lead to more prescription of antidepressants (OR = 1.07; 95% CI: 0.52-2.19) or referral to specialist mental health services (OR = 1.62; 95% CI: 0.72-3.64). Patients in the intervention group reported better accessibility of care (effect size (ES) = 0.4; p < 0.05) and provision of information and advice (ES = 0.5; p < 0.05). Conclusions: A tailored implementation programme may enhance the recognition and treatment of patients with anxiety or depression. Further development and evaluation of the programme is warranted to determine its cost-effectiveness.