(1) Background: The high prevalence of childhood obesity and its multicausal etiology make it necessary to approach it through different strategies, whose objective is to promote the physical, mental, and social well-being of children. Regular physical activity, in addition to having positive effects on the physical environment of those who practice it, influences positively in psychological aspects such as anxiety and depression, which are very frequent in children with obesity and overweight. (2) Objective: To analyze the changes produced by a program of physical exercise based on anthropometric indicators and levels of anxiety and depression in a population of Mexican children with obesity. (3) Methods: A longitudinal study with experimental group (EG) and control group (CG). The analysis population consisted of 105 children with a body mass index (BMI) for their gender and age group above the 95th percentile, of which 60 were girls and 45 were boys, with a mean age of 10.02 years (SD ± 0.79). By randomizing the participants, 54 were part of the EG and 51 of the, CG The EG participated in a physical exercise program, distributed in two weekly sessions, each lasting 50 minutes, for 20 consecutive weeks. The CG group continued its usual activities during the intervention period. An inferential analysis was performed between the socio-demographic, anthropometric and psychological variables. (4) Results: The implementation of a physical exercise program in children with obesity favors the appearance of positive thoughts, with improvements in their emotional well-being, self-perception and self-concept; although it does not produce significant changes in weight, height, Z-Score, level of anxiety or depressive thoughts. (5) Discussion: Regular physical exercise practice has positive effects on mental health, although new studies are required to analyze specifically its influence on anxiety and depression in children with obesity.