Kyrkja har fått namn etter kong Eystein Magnusson som var konte i Norge i åra 1103-1123. Soga fortel at kong Eystein bygde sælehus på Dovrefjell. I en mannjamning med broren Sigurd Jorsalfar skal desse orda ha falle: "På Dovre lot jeg bygge fjellstuer. Her frøs mange reisende i hjel før. Det er kanskje småting, men Norges folk er bedre tjent med at jeg bygger fjellstuer enn at du i Serkland slaktet blåmenn og sendte dem til helvete".
Ingvald Skaare (sokneprest i Dovre 1938-54) foreslo i 1947-48 at ein skulle attreise den gamle Hjerkinn-kyrkja som eit minne om kong Eystein. Det var mange meiningar og drøftingar om tomteval før det vart semje om plassen ved Hjerkinn fjellstue.
Eysteinkyrkja er teikna av arkitekt Magnus Poulsson med sonen Anton Poulsson som utførande arkitekt. Grunnstein lagt ned 6. oktober 1963 av biskop Kristian Scheldrup, og kyrkja vart vigsla av biskop Alex Johnsom 3. august 1969.
Kyrkja er støypt i betong med stein og sand frå gruva på Tverrfjellet, og ein kan sjå at det glitrar i svovelkis i somme ljoshøve. Kvelven er prikk-hamra. Byggmeister Høyer-Ellefsen med Ivar Bakken som byggeleiar. Dører, smijernbeslag, salmebokhyller m.m. er laga av lokale håndverkarar. Mykje av kyrkjeutstyret er gåver frå bygdafolk og andre.
Kyrkja er ei langplan kyrke med vifteform, og den har 110 sitteplasser. Med sin spesielle arkitektur og plassering er den eit landemerke på Dovrefjell. Kyrkja er open for besøk i sommar-sesongen.