Samtidig tyder mye på at Magnus, som idealiserte sin farfar, ønsket å gjenreise de norske kongenes dominans i vesterhavet.

Men før Magnus kunn e ta fatt på den oppgaven, blusset det opp en ny konflikt på hjemmebane. I Magnus’ fravær hadde Tore på Steig forsøkt å få en viss Svein Haraldsson utropt til konge i Trøndelag. Svein svar en eldre mann, og ifølge enkelte historikere var han trolig en uekte sønn av Harald Hardråde. Dette ga kravet en viss legitimitet og kunne derfor skape en alvorlig situasjon for Magnus. Tore og Svein fikk følge av et par lendmenn, og i begynnelsen hadde de en viss framgang i Trøndelag, men da flokken vendte sørover fra et herjetog nordpå, ble de møtt av Magnus’ krigsvante tropper og slått på flukt. Tore ble fanget og hengt, mens Svein klarte å rømme til Danmark. Han kom senere tilbake og ble hirdmann hos kong Øystein Magnusson.

Etter å ha knust dette opprøret ser Magnus ut til å ha hatt et fast grep om makten innenlands. Kongedømmet hans ble nå forankret i et nettverk av mektige lendmenn rundt om i landet. Mange av dem var også i nær familie med Magnus. Disse forbindelsene integrerte kongeverdigheten i aristokratiet på en måte som ikke hadde vært tilfelle tidligere, samtidig som aristokratiet nå ble nødt til å søke makt og innflytelse i samarbeid med kongen. Dette sikret Magnus ryggen fri til å planlegge sitt store tokt til vesterhavsøyene.

I 1098 utrustet han ifølge kildene 60 skip med vel 5000 mann om bord og dro vestover til Orknøyene. Dette er det samme antallet menn som farfaren Harald Hardråde mønstret i Norge før sitt felttog, noe som betyr at den norske offensive kapasiteten nå var tilbake på 1066-nivå bare 30 år etter mannefallet ved Stamford Bridge. Harald hadde da kalt ut halve leidangen, og trolig gjorde Magnus det samme. Det ville vært vanskelig å få gjennomslag for at en større andel av bøndene skulle bli utkalt til krigstjeneste uten at det var krig i landet, og det ville dessuten være svært uansvarlig med tanke på matproduksjonen.

Magnus befestet sitt overherredømme over Orknøyene og Shetland