Heinesen groeide op in een Deenstalig gezin in Tórshavn. Door zijn vader werd hij de Handelshogeschool in Kopenhagen ingelokt. Hiermee stopte hij echter al snel. Hij begon aan een journalistenopleiding in het Deense Ringsted, niet omdat hij journalist wilde worden, maar omdat zijn vriend, schrijver Jørgen-Frantz Jacobsen, in het nabijgelegen Sorø studeerde. Toen zijn vader getroffen werd door de Spaanse griep keerde hij terug naar de Faeröer, maar zijn vader bleek hersteld te zijn toen hij aankwam. Vervolgens trad hij in dienst bij het bedrijf van zijn vader als handelsconsulent. Hij maakte veel reizen, o.a. (samen met Jacobsen) naar Frankrijk. Toen hij trouwde stopte hij met reizen en bleef op de Faeröer.
Als 21-jarige gaf Heinesen zijn eerste dichtbundel uit: Arktiske Elegier og andre Digte (Arctische elegieën en andere gedichten, 1921). Toen hij hoorde dat de Deense dichter Nis Petersen rijk geworden was met het schrijven van een dikke roman, besloot Heinesen hetzelfde te doen. Dat resulteerde in de roman Blæsende gry (Winderige dageraad, 1934). Het boek kreeg wisselende kritieken. Pas na de Tweede Wereldoorlog werd hij een grote naam na het verschijnen van de romans Den sorte gryde (De zwarte pan, 1949) en De fortabte spillemænd (De verloren speelmannen, 1950).
Erkenning
Hoewel Heinesen de meest gelezen schrijver is buiten de Faeröer zelf, wordt hij op de eilanden zelf nauwelijks gelezen. De belangrijkste reden hiervoor is dat Heinesen in het Deens schreef en niet in het Faeröers. Heinesen was het Faeröers wel machtig, maar zag het Deens als zijn moedertaal en de taal waarin hij zichzelf het beste kon uitdrukken.
Verder was Heinesen links georiënteerd. Hij had contact met Deense communistische schrijvers als Hans Scherfig, Hans Kirk en Otto Gelsted. Bovendien maakte hij vaak de kerk belachelijk in zijn werk. Deze twee zaken rijmden niet met de conservatieve en religieuze samenleving op de Faeröer. Buiten de Faeröer, met name in Denemarken, had Heinesen wel succes.
In 1965 won Heinesen de Literatuurprijs van de Noordse Raad voor zijn roman Det gode håb (De goede hoop, 1964). Ook gingen er geruchten dat hij de Nobelprijs voor de Literatuur in 1981 zou winnen. Als antwoord daarop schreef hij een brief aan de Zweedse Academie waarin hij afstand deed van de kandidatuur. Later verklaarde hij dat het een slag voor de eigen cultuur van de Faeröer zou zijn geweest als een Deenstalige schrijver de prijs had gewonnen. De Deense koning onderscheidde hem met de exclusieve medaille "Ingenio et Arti".
In 1985 werd aan hem de Deense Sonningprijs toegekend.
Ondanks de tegenstand die hij op de Faeröer ondervond, werd hij uitgeroepen tot ereburger van Tórshavn. Ook kwam zijn portret nog tijdens zijn leven op een postzegel.
In 2017 heeft Atlantic Airways hun nieuw in gebruik genomen vliegtuig vernoemd naar hem.
