Background: Recommendations have been proposed for minimum aerobic fitness among firefighters but it is unclear if those criteria relate to performance on the fireground. Less fit individuals fatigue more quickly than fit individuals when working at comparable intensity and may have gait changes, increasing risk of falls. We evaluated the effect of fatigue during a live burn evolution on gait parameters and functional balance comparing them to aerobic fitness levels. Methods: A total of 24 firefighters had gait and balance tested before and after a live burn evolution. Data were stratified by aerobic fitness of greater/less than 14 metabolic equivalents (METs). Results: Analysis of gait cycles measurements before and after the live burn evolution revealed that single leg stance, cycle, and swing time decreased (p < 0.05) but there were no differences in the other measures. There were no differences in time to complete the functional balance test, or errors committed before or after a live burn evolution. When firefighters were sorted by fitness level of 14 METs, there were no differences for errors or time before or after the live burn evolution. Balance data were analyzed using a linear regression. Individuals with lower fitness levels required more time to complete the test. Conclusion: A 14-MET criterion failed to distinguish gait or balance characteristics in this group. However, less fit firefighters did require more time to complete the balance test (p = 0.003). Aerobic fitness alone does not predict gait changes among firefighters following a live burn evolution but does appear to influence functional balance.