Background: Several studies have shown that acute exercise has a small positive effect on cognitive performance. However, it is still unclear what type of exercise has a sustained impact on cognitive performance during post-exercise recovery. Therefore, the purpose of our study was to investigate cognitive performance at the behavioral level, and their neural correlates after a 10-minute post-exercise recovery period with two different types of exercise intervention (high-intensity interval exercise (HIIE) vs. Moderate-intensity continuous exercise (MCE)). Methods: A total of 29 healthy young adults (7 women) between the ages of 19 and 33 with fair to good cardiovascular fitness were submitted to two different exercise protocols and a recovery session. Cognitive function was assessed using a digital Trail-Making-Test (dTMT). Cortical activity in the prefrontal and the motor cortex using functional near-infrared spectroscopy (fNIRS) was measured before, after acute exercise, and during recovery. The statistical analysis of fNIRS data was performed by comparing the slope and mean of the hemodynamic response. Results: High levels of hemodynamic responses were observed in the prefrontal and motor cortex on the brain during performing the dTMT while walking from pre- to post-exercise and decreased again in post-recovery, accompanied by improvement and maintenance of cognitive performance. Notably, a high hemodynamic response in the left motor area of the brain was maintained by HIIE in post-recovery compared with MCE. Conclusions: The high cortical activation in the left motor area from post-exercise to recovery for the HIIE group may be due to the additional availability of neural resources for fine motor and postural control by high-intensity exercise-induced fatigue. Additionally, the improved cognitive performance may have effectively utilized the available neural resources in the frontal lobe, depending on the condition (sitting and walking) and the two types of exercise protocol (HIIE and MCE).