Dobio je ime po liku iz nordijske mitologije, koji je sastav nazvao „zapanjujućim” i koji je nekoliko puta spomenut u stihovima Enslavedovih pjesama; skupina ga je prvi put spomenula na Yggdrasillu, drugom demouratku, koji je objavljen 1992.[9] Na albumu se nalazi šest novih pjesama i pjesma „Caravans to the Outer Worlds”, prethodno objavljena na istoimenu EP-u iz 2021.[10] Grupa je objavila taj EP kako bi povezala prethodni studijski album Utgard (iz 2020.) i Heimdal te je zaključila da se pjesma „Caravans to the Outer Worlds” uklapa u novi album i glazbom i stihovima.[9]
Dobio je uglavnom pozitivne kritike. Na Metacriticu, sajtu koji prikuplja ocjene recenzenata raznih publikacija i na temelju njih uratku daje prosječnu ocjenu od 0 do 100, uradak je na temelju četiri recenzije osvojio 80 boda od njih 100, što označava „uglavnom pozitivne kritike”.[11] Pišući za časopis Kerrang!, Nick Ruskell dao mu je četiri boda od njih pet i izjavio je: „Poslije šesnaest albuma i dalje iznenađuju i stvaraju – to treba posebno pohvaliti. Budući da je to najbolji rad [sastava] u proteklih deset godina, to je trijumf zaista veličanstvene skupine.”[1] David E. Gehlke bio je slična mišljenja u svojoj recenziji za Blabbermouth; dao mu je osam od deset bodova izjavivši da „[n]akon više od trideset godina i 16 studijskih albuma ENSLAVED, zadivljujuće, i dalje ostaje vjeran svojim korijenima dok definira progresiju ekstremnog metala.”[12]
Max Morin dao mu je devet od deset bodova u recenziji za Metal Injection napisavši: „Na Heimdalu su se [članovi skupine] najdalje odmaknuli od svoje sigurne zone. To je također jedan od najboljih albuma koje su dosad objavili.”[14] U recenziji za Sputnikmusic Fernando Alves dao mu je četiri boda od njih pet napisavši: „Heimdal djeluje prirodnije od svojih nedavnih prethodnika; manje je dotjeran i stoga siroviji, no pritom i dalje ostaje složen i poduzetan.”[17] Dave Everley dao mu je šest bodova od njih deset u recenziji za časopis Classic Rock zaključivši: „Malo će toga iznenaditi bilo koga tko je poslušao bilo koji od Heimdalovih 15 prethodnika, osobe osjetljivijih ušiju neće moći progutati neke ekstremnije trenutke, ali sve u svemu, to je i dalje dojmljiv [album].”[13]
