Det han lyktes minst med, var å bygge opp lojalitetsnett og vennskapsbånd til stormennene, som følte seg truet av en voksende sentral kongemakt. Dette var daneveldets storhetstid, og i England regjerte den mektige danskekongen Knud, som ønsket å gjenerobre Norge. Han kjøpte seg lojalitet hos de norske lederne. Blant bøndene i innlandet, i Trøndelag og nordpå vokste også misnøyen med Olavs «hardstyre», neppe fordi han styrte hardere enn andre, men fordi han insisterte på å styre. Folk trodde tøylene ville bli slappe som før under en konge som satt så betryggende langt borte som Knud.
Makten smuldret under kong Olav, og han måtte flykte. Sitt siste leveår tilbrakte han hos svogeren storfyrst Jaroslav i Kiev, en by som allerede var blitt et åndelig sentrum i det østlige Europa, med sterk oppblomstring i teologi og filosofi, klostervesen og kunst.
I 1030 dro han hjemover for å prøve å gjenerobre makten. Det avgjørende slaget kom til å stå på Stiklestad 29. juli. Men motstanderne var overmektige i antall og slagkraft, og kongen falt. Liket ble smuglet bort og gravd ned i en sandmeling der Nidarosdomen nå ligger.
Snart begynte underlige ting å skje. En solformørkelse ble umiddelbart koblet til slaget, som et bud om himmelens vrede og et tegn på at Stiklestad lå i avglansen fra Golgata, der det også ble «mørke midt på dagen». Det gikk gjetord om plutselige helbredelser, blant annet fikk en av kongens banemenn, Tore Hund, leget et sår i hånden da et stenk av kongens blod kom på det, og han brøt opp og dro på botsferd til Jerusalem.
Vel et år etter kongens fall ble liket gravd opp, og biskopen erklærte ham med folkets tilslutning som en hellig mann. Helgenkåringer var den gang lokalkirkens sak, men Olavs helgenverdighet ble fullt anerkjent av paven i Rom.
Olav ble helligkåret som martyr. Det var hans død under korsmerket som ble fremholdt som det sikre tegn på at Gud hadde brukt ham som redskap. Kåringen var altså ikke en vandelsattest for et uvanlig dydig livsløp. Men dessuten ble han æret som Norges apostel, fordi det var han som fullførte den lange kristningsprosessen.
Kombinasjonen av martyr og apostel var enestående, og er kanskje den viktigste forklaringen på at olavs-kulten ble så sterk og nådde så vidt.