Abstract: Cognitive Behavioral Therapy (CBT) has been proven an effective tool to address anger and anxiety issues in children and adolescents with Autism Spectrum Disorders (ASD). Robot-enhanced therapy has been used in psychosocial and educational interventions for children with ASD with promising results. Whenever CBT-based techniques were incorporated in robot-based interventions, they were mainly performed in group sessions. Objectives: The study’s main objective was the implementation and evaluation of the effectiveness of a relaxation training intervention for children with ASD, delivered by the social robot NAO. Methods: 20 children (aged 7–12 years) were randomly assigned to 16 sessions of relaxation training implemented twice a week. Two groups were formed: the NAO group (children participated in individual sessions with the support of NAO) and the control group (children participated in individual sessions with the support of the therapist only). Participants received three different relaxation scenarios of increasing difficulty (a breathing scenario, a progressive muscle relaxation scenario and a body scan medication scenario), as well as related homework sheets for practicing. Pre- and post-intervention assessments were conducted using the Child Behavior Checklist (CBCL) and the Strengths and Difficulties Questionnaire for parents (SDQ-P). Participants were also asked to complete an open-ended questionnaire to evaluate the effectiveness of the training. Parents’ satisfaction was evaluated via a questionnaire and children satisfaction was assessed by a thermometer scale. Results: The study supports the use of relaxation training with the NAO robot as instructor for children with ASD. Parents of enrolled children reported high levels of satisfaction and provided positive ratings of the training acceptability. Children in the NAO group presented greater motivation to complete homework and adopt the learned techniques at home. Conclusions: Relaxation training could be effectively integrated in robot-assisted protocols to help children with ASD regulate emotions and develop self-control.