Individuals do not have complete information about the environment and therefore they face a trade-off between gathering information (exploration) and gathering resources (exploitation). Studies have shown individual differences in components of this trade-off but how stable these strategies are in a population and the intrinsic drivers of these differences is not well understood. Top marine predators are expected to experience a particularly strong trade-off as many species have large foraging ranges and their prey often have a patchy distribution. This environment leads these species to exhibit pronounced exploration and exploitation phases but differences between individuals are poorly resolved. Personality differences are known to be important in foraging behaviour but also in the trade-off between exploration and exploitation. Here we test whether personality predicts an individual exploration-exploitation strategy using wide ranging wandering albatrosses (Diomedea exulans) as a model system. Using GPS tracking data from 276 wandering albatrosses, we extract foraging parameters indicative of exploration (searching) and exploitation (foraging) and show that foraging effort, time in patch and size of patch are strongly correlated, demonstrating these are indicative of an exploration-exploitation strategy. Furthermore, we show these are consistent within individuals and appear stable in the population, with no reproductive advantage. The searching and foraging behaviour of bolder birds placed them towards the exploration end of the trade-off, whereas shy birds showed greater exploitation. This result provides a mechanism through which individual foraging strategies may emerge. Age and sex affected components of the trade-off, but not the trade-off itself, suggesting these factors may drive behavioural compensation to maintain resource acquisition and this was supported by the evidence that there were no fitness consequence of any EE trait nor the trade-off itself. These results demonstrate a clear trade-off between information gathering and exploitation of prey patches, and reveals for the first time that boldness may drive these differences. This provides a mechanism through which widely reported links between personality and foraging may emerge.