Physical exercise is widely reported beneficial to executive functions in children with autism spectrum disorder. However, its impact on self-regulation in the population remains unknown. This study is to test whether two types of physical exercise (cognitively engaging vs non-cognitively engaging) benefited self-regulation and whether the social, emotional, and physical needs of an individual mediated the exercise--executive function and exercise--self-regulation relationships. Sixty-four children diagnosed with autism spectrum disorder were randomly assigned into 1 of 3 groups: learning to ride a bicycle (n = 23), stationary cycling (n = 19), or an active control with walking (n = 22). Two executive functions (flexibility and inhibition), self-regulation and the mediating roles of perceived social support, enjoyment, stress, physical self-efficacy, and perceived physical fitness were assessed. Participants in the learning to ride a bicycle group significantly improved their executive functions (p values < 0.01). The learning to ride a bicycle group and the stationary cycling group also significantly enhanced their self-regulation (p values < 0.001). Mediation analyses showed that physical self-efficacy and perceived physical fitness partially mediated the exercise--executive function relationship. Meanwhile, perceived social support significantly mediated the exercise--self-regulation relationship (p < 0.05). Our findings highlight the value of cognitively engaging exercise on enhancing executive functions in children with autism spectrum disorder in part by improving their physical self-efficacy and perceptions of fitness.