Den mytiske realisme, som i nogen grad er at finde i ”Den sorte gryde” fandt sin færdige form i skæmteromanen ”De fortabte spillemænd” og udvikledes herefter gennem Heinesens mest mytiske og poetisk kalejdoskopiske romaner ”Moder syvstjerne” og ”Tårnet ved verdens ende” samt i de mange novellesamlinger, som kom i perioden fra 1957 til 1985. Denne del af forfatterskabet er vel at regne for Heinesens mest blivende og originale bidrag til litteraturhistorien. Man må dog ikke glemme, at Heinesen tillige var en vigtig lyriker i især mellemkrigsårerne, hvor han i perioden 1921 til 1936 udgav fem digtsamlinger, som gjorde ham til en navnkundig poet, der måtte kæmpe hårdt for også at blive anerkendt som prosaist. Digtene var kendetegnet ved en stærk naturfølelse, og Heinesen har selv udtalt at den kosmiske følelse er uundgåelig på Færøerne. De små øer fylder ikke meget mellem Himlen og havet, som til gengæld fylder meget i både synsfeltet og bevidstheden hos færingerne og er helt centrale motiver i Heinesens digte. Havet og himlen er farlige kræfter, der grådigt sluger skibe og suger huse løs fra grunden.
Samtidig er de dog også de alfaderlige elementer, som ordner verden i et meningsfuldt hele. De er altings perspektiv, og allerede i denne opfattelse af naturen får man et indtryk af den mytiske virkelighedsopfattelse, som i prosaforfatterskabet skal komme til at spille en afgørende rolle. Himlens og havets guder Poseidon og Zeus er ikke vigtige som eksplicitte motiver i digtene, men implicit hersker de i stort set hver eneste linje.
Efter at have udgivet sine fire første digtsamlinger, forsøgte Heinesen at bryde igennem hos et større publikum ved hjælp af prosaens folkelige gennemslagskraft. Debutromanen ”Blæsende gry” fra 1934 blev dog ikke nogen succes, og den blev kritiseret for at være for ambitiøs og have for mange løse ender. Det var en socialt engageret murstensroman, men Heinesens komposition lå fjernt fra datidens danske socialrealisme og kritiske realismes logisk fremadskridende fortællerytme. Han åbenbarede sin verden i små bidder, som læseren så selv måtte stykke sammen til et hele. Denne tendens til at skrive en lyrisk og fragmenteret prosa har dog, på trods af debutromanens manglende succes, i det væsentlige holdt sig gennem hele forfatterskabet. Efter ”Blæsende gry” (som i 1961 blev redigeret ned til et kun halvt så langt og meget strammere komponeret værk) udkom i 1938 "Noatun", der fik en mere nådig modtagelse af både publikum og anmeldere. Efter denne ligeledes socialt engagerede roman begyndte Heinesen den del af sit forfatterskab, som gennem årerne fik flere kritikere til at se ham som en værdig nobelpriskandidat. Menneskene i romanerne og novellerne der fulgte herefter var stadig realistiske og de lyriske beskrivelser allestedsnærværende. Den kosmiske fornemmelse fra digtene spiller ligeledes en afgørende rolle. Niveauet er dog ganske enkelt blevet hævet, idet Heinesen er blevet en mere øvet romanforfatter og har fundet frem til en stil, hvor han kan forlene ovenstående karakteristika med en løssluppen humor, der bæres af groteske og bizarre hændelser og beskrivelser, uden dermed at give køb på alvoren. Han forfalder aldrig til blot at fiske efter et grin. Smerten og tragedien ikke blot lurer, men er åbenlyst til stede midt i al morskaben, og de poetiske skildringer bliver aldrig distanceret skønmaleri, men fremhæver tværtimod menneskets farlige magt og menneskets magtesløshed i verden.
Som mere atypiske udgivelser i den sidste del af forfatterskabet udsendte Heinesen de to digtsamlinger ”Hymne og harmsang” (1961) og ”Panorama med regnbue” (1972) samt middelalderromanen fra Færøerne ”Det gode håb” (1964).