The requirement to maintain and uplift fuel in naval vessels is a necessary operating constraint and, with projections forecasting that fuel oil prices will continue to rise, uplifts need to be scheduled to deconflict with military tasking whilst being financially efficient. This paper presents mission fuel management as an optimisation problem, where analytical techniques are used to explore the impact of intelligent uplifts, intelligent leg speeds and the impact of minimum fuel holding restrictions and hull bio-fouling. Using a representative transit, we demonstrate that relative fuel price differences between ports may be exploited to achieve mission fuel cost savings of 15% to 25%, without impacting mission dates. For time constrained transits, being those with leg speeds limited by the minimum fuel holding restriction, a saving of 4% to 5% is achievable by varying leg speeds. Finally, we conclude that challenging minimum fuel holding requirements can yield up to 5% saving, whilst hull bio-fouling has an almost negligible effect in our model (due to the short time at sea). Extrapolation indicates that whilst fuel consumption will invariably increase for a given speed, it does not affect the fuel uplift decision making.