Mental health and sleep problems are prevalent in children during preschool years. The aim of the current study was to investigate if increased intake of fatty fish compared with meat improves mental health and sleep in four- to six-year-old children. The children (n = 232) in the two-armed randomized controlled trial, Fish Intervention Studies-KIDS (FINS-KIDS), were randomly assigned to lunch meals with fatty fish (herring/mackerel) or meat (chicken/lamb/beef) three times a week for 16 weeks. The fish and meat were weighed before and after the meals to record the exact consumption in grams (dietary compliance). Mental health problems were assessed by the strengths and difficulties questionnaire (SDQ) and sleep by parent report pre- and post-intervention. There was no significant statistical difference between changes in mental health and sleep for the fish eating group compared with the meat eating group, neither in the crude analysis nor after adjusting for intake of fish or meat (dietary compliance).