This study explored the effects of exercise modality and type of fitness index on cognitive function in the older adults as assessed via behavioral and neuroelectrical approaches. Sixty older adults were assigned to an aerobic exercise, a coordination exercise, or a control group based on their previous exercise experience. The participants completed congruent and incongruent trials of a modified Stroop Test, during which, event-related potentials were recorded. The participants also completed multiple physical tests that assessed health- and skill-related fitness. Our findings suggest that, in general, both aerobic and coordination exercise, as well as higher scores on health- and skill-related fitness indices, are positively associated with better performance of various cognitive functions in the elderly population. The mechanisms underlying these relationships may be differentially related to specific neuroelectrical processes involved in neurocognitive control.