Background: The prevalence of patients with mental health problems in general practice is high, and at least one-third of these problems last for 6 months or longer. Patients with these problems take up more time during a consultation and attend more frequently. Aim: This study investigated the effectiveness of problem-solving treatment for primary care patients with mental health problems. The hypothesis was that patients receiving problem-solving treatment from a nurse would have fewer symptoms after 3 months, or a lower attendance rate, compared with patients receiving the usual care from the GP. Design of the study: Randomised clinical trial. Setting: Twelve general practices in Amsterdam and 12 nurses from a mental healthcare institution. Method: A sample of patients aged ≥18 years were screened for mental health problems with the general health questionnaire (GHQ-12) in the waiting room of the general practices, and were randomised. Patients receiving the problem-solving treatment were required to complete four to six treatment sessions, while patients in the control group were treated as usual by the GP. Results: No significant difference was found between the groups in terms of improved psychopathology or a decrease in attendance rate. Post-hoc analyses showed a sub-group of patients with more severe pathology who may benefit from problem-solving treatment. Conclusion: The main results show that problem-solving treatment provided by a nurse adds little to the usual care from the GP for frequent attenders with mental health problems. Post-hoc analyses show that there may be a sub-group of more severely depressed patients who could benefit from problem-solving treatment. © British Journal of General Practice 2007.