Critical surgical and medical advances have shifted the focus of congenital heart disease (CHD) patients from survival to achievement of a greater health-related quality of life (HRQoL). HRQoL is influenced, amongst other factors, by aerobic capacity and respiratory muscle strength, both of which are reduced in CHD patients. This study evaluates the influence of a cardiopulmonary rehabilitation program (CPRP) on respiratory muscle strength and functional capacity. Fifteen CHD patients, ages 12 to 16, with reduced aerobic capacity in cardiopulmonary exercise testing (CPET) were enrolled in a CPRP involving strength and aerobic training for three months. Measurements for comparison were obtained at the start, end, and six months after the CPRP. A significant improvement of inspiratory muscle strength was evidenced (maximum inspiratory pressure 21 cm H2O, 23%, p < 0.01). The six-minute walking test showed a statistically and clinically significant rise in walked distance (48 m, p < 0.01) and a reduction in muscle fatigue (1.7 out of 10 points, p = 0.017). These results suggest CPRP could potentially improve respiratory muscle function and functional capacity, with lasting results, in children with congenital heart disease, but additional clinical trials must be conducted to confirm this finding.