Animal behaviour exhibits fractal structure in space and time. Fractal properties in animal space-use have been explored extensively under the Lévy flight foraging hypothesis, but studies of behaviour change itself through time are rarer, have typically used shorter sequences generated in the laboratory, and generally lack critical assessment of their results. We thus performed an in-depth analysis of fractal time in binary dive sequences collected via bio-logging from free-ranging little penguins (Eudyptula minor) across full-day foraging trips (2¹⁶ data points; 4 orders of temporal magnitude). Results from 4 fractal methods show that dive sequences are long-range dependent and persistent across ca. 2 orders of magnitude. This fractal structure correlated with trip length and time spent underwater, but individual traits had little effect. Fractal time is a fundamental characteristic of penguin foraging behaviour, and its investigation is thus a promising avenue for research on interactions between animals and their environments.