Wildfire is a dominant disturbance agent in forest ecosystems, shaping important biogeochemical processes including net carbon (C) balance. Long-term monitoring and chronosequence studies highlight a resilience of biogeochemical properties to large, stand-replacing, high-severity fire events. In contrast, the consequences of repeated fires or temporal variability in a fire regime (e.g., the characteristic timing or severity of fire) are largely unknown, yet theory suggests that such variability could strongly influence forest C trajectories (i.e., future states or directions) for millennia. Here we combine a 4500-year paleoecological record of fire activity with ecosystem modeling to investigate how fire-regime variability impacts soil C and net ecosystem carbon balance. We found that C trajectories in a paleo-informed scenario differed significantly from an equilibrium scenario (with a constant fire return interval), largely due to variability in the timing and severity of past fires. Paleo-informed scenarios contained multi-century periods of positive and negative net ecosystem C balance, with magnitudes significantly larger than observed under the equilibrium scenario. Further, this variability created legacies in soil C trajectories that lasted for millennia. Our results imply that fire-regime variability is a major driver of C trajectories in stand-replacing fire regimes. Predicting carbon balance in these systems, therefore, will depend strongly on the ability of ecosystem models to represent a realistic range of fire-regime variability over the past several centuries to millennia.