Head and neck cancer survivors frequently experience nutritional challenges, and proper rehabilitation should be offered. The trial objective was to test the effect of a multidisciplinary residential nutritional rehabilitation programme addressing physical, psychological, and social aspects of eating problems after treatment. In a randomized controlled trial, 71 head and neck cancer survivors recruited through a nationwide survey were randomized to the program or a wait-list control group. Inclusion was based on self-reported interest in participation. The primary outcome was change in body weight. Secondary outcomes included physical function, quality of life, and symptoms of anxiety and depression. Differences between groups at the 3-month follow-up were tested. No significant differences were seen in body weight change, but there were overall trends towards greater improvements in physical function (hand grip strength: p = 0.042; maximal mouth opening: p = 0.072) and quality of life (“Role functioning”: p = 0.041; “Speech problems”: p = 0.040; “Pain”: p = 0.048) in the intervention group. To conclude, a multidisciplinary residential nutritional rehabilitation program had no effect on body weight in head and neck cancer survivors with self-reported interest in participation, but it may have effect on physical function and quality of life. Further research on relevant outcomes, inclusion criteria, and the program’s effect in different subgroups is needed.