Hederstierna anställdes vid tolv års ålder som volontär vid amiralitetet och trädde kort därpå i utländsk sjötjänst. Han tjänade under flera nationers flaggor och deltog i ett flertal sjöslag, bland annat den franskabelägringen av kastellet Palamós på Costa Brava i Katalonien. År 1697 utnämndes Hederstierna till underlöjtnant och 1700 till kapten, och deltog som sådan på en mängd uppdrag i de finska farvattnen.
Som chef för Hallands enrolleringskompani förde Hederstierna ofta befälet på skeppet Enigheten, bland annat under sjöslaget vid Rügen 1715. Då amiral Mikael Henck, som var den egentlige skeppschefen, stupade i början av slaget, övertog Hederstierna befälet och förde det med sådan skicklighet, att ingen under slaget märkt vad som inträffat. För sina insatser befordrades han samma år till kommendör och adlades 1717 med namnet Hederstierna. 1722 befordrades Hederstierna till schoutbynacht.
