Skule Storheill utmerket seg som sjøoffiser under den annen verdenskrig, da han var skipssjef på krigsfartøyer i fremste linje. Som sjef for Sjøforsvaret etter krigen deltok han i utformingen av Sjøforsvaret og gjorde en betydelig innsats i utviklingen av totalforsvaret av Nord-Norge.
Storheill vokste opp i Brønnøysund, og etter fartstid i handelsflåten kom han inn på Sjøkrigsskolen i Horten. Han ble sjøoffiser 1928, fastlønnet løytnant 1931 og inspeksjonsoffiser ved Sjøkrigsskolen 1936.
I denne funksjonen ledet Storheill flere av skolens elever fra det tyskbesatte Horten til innsats i det frie Nord-Norge i april–mai 1940. Her ble han selv forbindelsesoffiser til den britiske admiral Cunningham på krysseren Devonshire, som bare uker senere evakuerte kong Haakon 7 og regjeringen Nygaardsvold fra Tromsø til Storbritannia. Storheill ble sendt videre til Canada, hvor han deltok i bevæpningen av en rekke hvalbåter som den norske eksilmarinen overtok, og ble etter hvert kapteinløytnant.
Som kaptein 1941 ble han skipssjef på jageren St. Albans, som utmerket seg i konvoitjeneste. Han ble orlogskaptein 1942 og overtok den nybygde jageren Eskdale, som han deltok med i den allierte landgangen i Nord-Afrika høsten 1942. Eskdale ble senket i kamp med tyske styrker i Kanalen 1943, og Storheill overtok deretter kommandoen på den nybygde jageren Stord, som under hans ledelse deltok i senkingen av det tyske slagskipet Scharnhorst ved Nordkapp julen 1943. For å få denne kommandoen hadde han frivillig gått ned i grad til kapteinløytnant igjen.
Etter å ha vært observatør ved invasjonen på Sicilia 1943, deltok Storheill med Stord under de alliertes landgang i Normandie juni 1944. Senere eskorterte han allierte konvoier i både Atlanterhavet og Nordishavet, og ved krigens slutt førte han norske myndigheter tilbake til Tromsø med Stord. Han ble kommandør og sjef for Sjøforsvarsstaben 1946, og 1949 ble han sjef for Kysteskadren, som han ønsket skulle være en sjøgående jagerstyrke, helst med en stor krysser som flaggskip, men det ble med planene for dette. Storheill ble viseadmiral 1951 og var til 1954 sjef for Sjøforsvaret etter strid mellom admiralene og forsvarministeren. Som sjef for Sjøforsvaret fikk han omgjort et stortingsvedtak om plassering av den nye sjøkrigsskolen, som ble flyttet til Bergen fra Oslo i stedet for tilbake til Horten.
Storheill ble så sjef for den norske militærmisjon til Washington, USA – marineattaché til USA og Canada 1954–58. Han var samtidig medlem av NATOs Militærkomité og forbindelsesoffiser til NATOs Atlanterhavskommando i Norfolk, Virginia, USA.
1958 overtok Storheill som Øverstkommanderende for Nord-Norge (ØKN) med hovedkvarter i Harstad. Samtidig ble ØKN underlagt NATOs nordkommando på Kolsås i tilfelle krig, men Storheill var som ØKN skeptisk til at flystyrkene i nord i et slikt tilfelle ikke var underlagt ham. Storheill flyttet med stillingen til Bodø 1963 og kunne i all stillhet åpne et nytt og større krigshovedkvarter på Reitan. Han hadde ansvaret i en periode da NATO endret strategi fra massiv gjengjeldelse til såkalt fleksibel respons, noe som resulterte i en stadig økende NATO-øvelsesvirksomhet i Nord-Norge fra 1964 av. Storheil var opptatt av at et manglende nasjonalt kompetent kommandosystem ville medføre at allierte styrker som opererte i Nord-Norge, ville bruke egne kommandolinjer utenfor norsk kontroll. Hans synspunkter medvirket til at Forsvarskommando Nord-Norge på Reitan ble etablert 1971 som en NATO-kommando.
Som øverstkommanderende var Storheill opptatt av å øke USAs og NATOs interesse for Nordflanken og forplikte alliansen til forsvaret av Nord-Norge gjennom styrkede relasjoner med NATOs kommandoer, økt alliert virksomhet og styrket posisjon for Reitan i kommandosystemet, noe som preget Forsvaret i Nord-Norge i de to tiårene som fulgte hans sjefsperiode.
Storheill avsluttet sin militære karriere som direktør ved Forsvarets Høgskole 1967–69 og levde sine siste år i Drøbak. Storheill ble ansett som en ramsalt og effektiv sjømann, som kom med følgende hjertesukk som skrivebordsoffiser: “Moroa har jeg bak meg – det er slutt med havet!”
Skule Storheill hadde en rekke utmerkelser, bl.a. Krigskorset med sverd, Deltagermedaljen og den britiske Distinguished Service Cross; han ble utnevnt til kommandør med stjerne av St. Olavs Orden 1953.