While many ectothermic species can withstand prolonged fasting without mortality, food-deprivation may have sublethal effects of ecological importance, including reductions in locomotor ability. Little is known about how such changes in performance in individual animals are related either to mass loss during food-deprivation or growth rate during re-feeding. This study followed changes in the maximum sprint swimming performance of individual European sea bass Dicentrarchus labrax throughout 45 days of food-deprivation and 30 days of re-feeding. Maximum sprint speed did not show a significant decline until 45 days of food deprivation. Among individuals, the reduction in sprinting speed at this time was not related to mass loss. After 30 days of re-feeding, mean sprinting speed had recovered to match that of control fish. Among individuals, however, maximum sprinting speed was negatively correlated with growth rate after the resumption of feeding. This suggests that the rapid compensatory growth that occurs during re-feeding after a prolonged fast carries a physiological cost in terms of reduced sprinting capacity, the extent of which shows continuous variation among individuals in relation to growth rate. The long-term repeatability of maximum sprint speed was low when fish were fasted or fed a maintenance ration, but was high among control fish fed to satiation. Fish that had been previously food deprived continued to show low repeatability in sprinting ability even after the initiation of ad libitum feeding, probably stemming from variation in compensatory growth among individuals and its associated negative effects on sprinting ability. Together these results suggest that food limitation can disrupt hierarchies of maximum sprint performance within populations. In the wild, the cumulative effects on locomotor capacity of fasting and re-feeding could lead to variable survival among individuals with different growth trajectories following a period of feed deprivation.