The fittest I've ever been was in the navy of course. During basic training we weren't allowed to walk unless instructed to do so while marching in formation. Apart from that, we had to either be running, doing some form of exercise, sitting in class, working, or asleep. At the start of training, I did the 3.2km run in 14:47 (we had to do it under 15 minutes). At the end of basic I did the run, then went half way out and back in again, in under the 15 minute mark.
What really helped with my fitness training then was this chap Gary Williamson, a former prison guard who went straight into the special forces here after basic. He decided, without any request from me whatsoever, to become my personal trainer. For example I'd get in from the day's activities at 6 or 7 pm, and he'd pop in and say "Get up, we're going for a run". So in addition to getting up at 5am, and working until the instructors decided it was time to stop, I had a lot of extra-curricular exercise. Lots of running, lots of gymnasium work, lots of push-ups and sit-ups all day every day, for three months.
We did things like march alternating between at the slow and at the double, all day, carrying L1A1, canteen, and full pack, in combat boots. That gets you fit.
When I went on to branch training at HMAS Watson, the PTs there thought it was a good idea to have us run up and down the hill for an hour carrying the free weights from the gym. Now in my class, most of the others ran up a little way from the gym, then ducked in behind the accommodation blocks, then waited until I'd reached the top and come down again, and joined in the running again. I was the only one to do the entire trip, every time, for the full hour, in every session. It may have been very stupid, but it got me very fit and strong.