Martin Sæterhaug reed al op 20-jarige leeftijd een internationaal schaatstoernooi. In 1903 werd hij achtste bij het EK Allround in Oslo.
Sæterhaug boekte vijf jaar later zijn eerste succes. Bij het WK Allround van 1908 in Davos werd de Noor tweede achter landgenoot Oscar Mathisen. Twee jaar later won hij brons bij het WK Allround van 1910 en een jaar later zilver. In 1912 boekte hij zijn enige podiumplaats bij een EK Allround, in Stockholm werd hij derde.
