(1) Introduction: Adolescents with complex congenital heart disease (CCHD) show brain tissue injuries in regions associated with cognitive deficits. Alteration in cerebral arterial perfusion (CAP), as measured by arterial transit time (ATT), may lead to perfusion deficits and potential injury. Our study aims to compare ATT values between CCHD patients and controls and assess the associations between ATT values, MD values, and cognitive scores in adolescents with CCHD. (2) Methods: 37 CCHD subjects, 14-18 years of age, who had undergone surgical palliation and 30 healthy controls completed cognitive testing and brain MRI assessments using a 3.0-Tesla scanner. ATT values and regional brain mean diffusivity [MD] were assessed for the whole brain using diffusion tensor imaging. (3) Results: The mean MoCA values [23.1 ± 4.1 vs. 28.1 ± 2.3; p < 0.001] and General Memory Index, with a subscore of WRAML2 [86.8 ± 15.4 vs. 110.3 ± 14.5; p < 0.001], showed significant cognitive deficits in CCHD patients compared to controls. The mean global ATT was significantly higher in CCHD patients versus controls (mean ± SD, s, 1.26 ± 0.11 vs. 1.19 ± 0.11, p = 0.03), respectively. The partial correlations between ATT values, MD values, and cognitive scores (p < 0.005) showed significant associations in areas including the hippocampus, prefrontal cortices, cerebellum, caudate, anterior and mid cingulate, insula, thalamus, and lingual gyrus. (4) Conclusions: Adolescents with CCHD had prolonged ATTs and showed correlation with clinical measurements of cognitive impairment and MRI measurements of brain tissue integrity. This suggests that altered CAP may play a role in brain tissue injury and cognitive impairment after surgical palliation.