The unemployment rate among newly arrived refugees in European countries is high and many experience mental health problems. This has negative consequences on integration and mental well-being. In this case series study we investigated the effect of a 30-week program that included horticulture activities, nature-based therapy, and traditional job training on job market affiliation and mental well-being. Fifty-two refugees met initial screening criteria and twenty-eight met all inclusion criteria and were enrolled. The program took place in a small community and consisted of informal therapeutic conversations, exercises aimed at reducing psychological stress, increasing mental awareness and physical wellbeing. At the end of the program traditional job market activities were led by social workers. Provisionary psychiatric interviews showed that at baseline 79% met criteria for either an anxiety, depression, or PTSD diagnosis. After the program, statistical analyses revealed an increase in the one-year incidence of job market affiliation (n = 28) and an increase in mental health according to two of four questionnaire measures (n_range = 15–16). The results strengthen the hypothesis that horticulture and nature-based therapy can help refugees enter the job market. However, the small sample size emphasizes the need for methodologically stronger studies to corroborate these preliminary findings.