Animals may use long-distance foraging trips to capitalize on spatiotemporal variation in food availability, allowing individuals to maximize resource gain from foraging effort. This is particularly important for dimorphic species with polygynous mating where males face strong selection pressures to attain large size and access to reproductive females. We tracked 17 male Antarctic fur seals, Arctocephalus gazella, during their prolonged postbreeding trips and assessed links between their movements and environmental predictors of profitable feeding areas. Males made one of two types of trips: a long trip to the Antarctic ice edge or shorter trips to areas where the southern Antarctic Circumpolar Current fronts generate high biological activity. The trip type was not determined by body size but was related to departure date from the breeding area, suggesting that males must trade off opportunities at the breeding area (reproductive, social interactions) and foraging opportunities between breeding seasons. Regardless of trip structure, males focused search effort far from foraging areas of central-place foraging seabirds and seals including female Antarctic fur seals provisioning offspring. Males showed clear spatiotemporal patterns in dive behaviour, with deep dives in shelf waters during the day and predominantly shallower dives in pelagic waters at night. Diel dive patterns showed monthly changes in photoperiod and lunar phase, consistent with feeding on vertically migrating prey. However, males did not use area-restricted search to focus dive effort, instead performing a mix of foraging and nonforaging behaviour within and between restricted search areas. We discuss the scale and type of inference that can be made from movement models, given the behavioural constraints that govern long-distance trips in vast, heterogeneous environments like the Southern Ocean.