Foraging theory predicts that breath-hold divers adjust the time spent foraging at depth relative to the energetic cost of swimming, which varies with buoyancy (body density). However, the buoyancy of diving animals varies as a function of their body condition, and the effects of these changes on swimming costs and foraging behaviour have been poorly examined. A novel animal-borne accelerometer was developed that recorded the number of flipper strokes, which allowed us to monitor the number of strokes per metre swam (hereafter, referred to as strokes-per-metre) by female northern elephant seals over their months-long, oceanic foraging migrations. As negatively buoyant seals increased their fat stores and buoyancy, the strokes-per-metre increased slightly in the buoyancy-aided direction (descending), but decreased significantly in the buoyancy-hindered direction (ascending), with associated changes in swim speed and gliding duration. Overall, the round-trip strokes-per-metre decreased and reached a minimum value when seals achieved neutral buoyancy. Consistent with foraging theory, seals stayed longer at foraging depths when their round-trip strokes-per-metre was less. Therefore, neutrally buoyant divers gained an energetic advantage via reduced swimming costs, which resulted in an increase in time spent foraging at depth, suggesting a foraging benefit of being fat.