De carrière eerst. Herfst '94 werd Colijn ingezet bij de expeditie naar Lombok. Drie dagen na aankomst moest hij zijn ziek-geworden kapitein als compagnies-cornmandant vervangen. Onder zijn leiding werd de kraton van de opstandige radja bestormd; het bezorgde hem de hoogste militaire onderscheiding, de Militaire Willemsorde. In '95 vertrok hij naar het onrustige Atjeh, maar niet zozeer uit liefde voor het militair bedrijf als wel uit bittere financiële noodzaak: er moesten schulden betaald worden en militairen in Atjeh kregen een hogere bezoldiging. Daar pas kon hij voor het eerst in zijn leven honderd gulden bijeensparen ; hij bood ze zijn vrouw op de zesde verjaardag van hun huwelijk' als een herinnering aan samen doorleefde zorgen met een dankbaar en gelukkig hart ... als verjaarsgeschenk' aan.! Enkele jaren lang nam Colijn aan de vaak wrede koloniale oorlog in Atjeh deel. Hij verwierf er de eresabel voor betoonde dapperheid; hij toonde er ook opvallende bestuurscapaciteiten. In I90I werd hij, tot kapitein bevorderd, adjudant van generaal van Heutsz. Toen deze als gouverneur-generaal optrad (I904-09), werd Colijn een van zijn naaste medewerkers, speciaal belast met het uitbrengen van adviezen over bestuurszaken in wat men de Buitenbezittingen noemde en het uitoefenen van controle daarop. Zijn werkkracht evenaarde zijn toewijding. 'Mijn gezin heb ik'
, schreef hij in 1909 aan de minister van koloniën, 'bij'
s lands dienst geheel ten achter gesteld: we zijn zestien jaar getrouwd en ruim elf was ik er niet van bij mijn gezin, waren vrouwen kinderen alleen, soms voor anderhalfjaar achtereen, voor perioden van drie tot zes maanden herhaaldelijk.P