Introduction: Executive function is responsive to exercise and predictive of subsequent falls. Minimal clinically important differences (MCIDs) are critical for understanding whether observed changes are meaningful. However, MCIDs of many cognitive measures are not established. We aimed to determine MCIDs of the Digit Symbol Substitution Test ([DSST] processing speed measure), Stroop (inhibition measure), and Trail Making Test B-A (TMT; set-shifting measure), using anchor- and distribution-based approaches in older adults who have fallen and received the Otago Exercise Program (OEP) relative to usual care only (CON). Our secondary aim was to establish construct (convergent and divergent) validity of these measures. Methods: Complete case analyses of cognitive outcomes (DSST, Stroop, TMT, and Montreal Cognitive Assessment [MoCA]) were acquired at baseline and 1 year (NCT01029171; NCT003235960); participants were randomized to the OEP (n = 114/172; Age: 80.6 ± 6.1 years; 64.9% Female) or CON (n = 128/172; Age: 82.3 ± 5.8 years; 71.9% Female)]. The MoCA was used as the anchor. We estimated MCIDs using anchor- and distribution-based approaches. Anchor-based executive function change differences ([CD] 1 year minus baseline) observed in participants with meaningful changes in the MoCA (≥3 or ≤ −3 points) receiving the OEP were subtracted from the CON. An anchor-based receiver operator characteristic (ROC) curve was employed to identify optimal cut-off scores of the 3 executive function measures. The distribution-based approach (DA) accounted for variability in baseline and follow-up data. MCID ranges were estimated using these approaches. We used Spearman’s correlations to explore convergent validity between executive function measures and other measures involving the same construct (DSST, Stroop, TMT, MoCA, and Mini-Mental State Examination), and divergent validity between executive function measures and variables reflecting different constructs (Geriatric Depression Scale, Instrumental Activities of Daily Living, sex, and body mass index). Results: Based on the 3 approaches, MCID improvement ranges were 3–5 symbols for the DSST (CD = 5; ROC = 2.5; DA = 3.3 symbols), and −11.5 to −26.0 s for the Stroop (CD = −26.0; ROC = −11.5; DA = −20.6 s). MCID decline ranges were −3 to −6 symbols for the DSST (CD = −5.2; ROC = −2.5; DA = −3.3 symbols) and 5.4–30.6 s for the Stroop (CD = 30.6; ROC = 5.4; DA = 20.6 s). MCIDs for the TMT were not meaningful due to high variability (Improvement: CD = −106.6; ROC = −18.4; DA = −69.1 s; Decline: CD = 69.1; ROC = 14.5; DA = 69.1 s). The executive function measures exhibited good convergent (r = −0.22 to r = 0.42) and divergent (r < −0.01 to r = 0.16) validity. Conclusions: These established MCIDs will allow clinicians to interpret meaningful changes in executive function following exercise amongst older adults who have fallen. The DSST, Stroop, and TMT demonstrated good construct validity, supporting their use in comprehensive fall-risk assessments in older adults who fall.