Gammal kyrkjestad
Sjølvaste Heilag-Olav skal ha stått her og blinka ut staden der kyrkja skulle stå. Runesteinen på Stedje er berre eitt av vitnemåla om at Stedje er ein av dei eldste kyrkjestadene i Sogn. I mellomalderen var kyrkja den største i Sogndal, og ho hadde status som hovudkyrkje eller fylkeskyrkje. Fyrste gongen ein finn henne omtala er i Sverre-soga i samband med at Sverre straffa sogndølene i 1184. Kyrkja stod på same staden som Stedje kyrkje står i dag. Kyrkjestaden er ein flat terrasse på vestsida av dalen.
Dagens kyrkje på Stedje vart reist i den store byggjeperioden her i landet i andre halvdelen av 1800-talet. Ho er ei av dei mest monumentale kyrkjene her i fylket. Den treskipa kyrkja er tydeleg inspirert av stavkyrkjestilen. Når ein stig inn i kyrkjerommet er glasmosaikken i dei indre veggene øvst i koret det mest iaugefallande. Vindauga vart sette inn i 1943, i samband med ei større restaurering som gjekk føre seg fram mot 1950. Vindauga mot nord og sør viser dei fire evangelistane, medan vindauget i austveggen viser krossfestinga, Maria og Johannes. Både desse bileta og glasmosaikken i sakristia er signert atelier J. Rognaldsen, Bergen. Alle bileta er sette saman av tre felt i breidda og avslutta med kløverbladforma øvst.
Koret har vegger høgt oppe, det er bygt med eit midtrom slik som kyrkjeskipet. I koret er midtskipet bore oppe av åtte søyler, og med bratte skråvegger ut mot sidene til den låge veggrekkja. Dei høge indre veggene er markert med brystning under vindauga. I sjølve kyrkjerommet er midtskipet skilt frå sideskipa med seks søyler. Oppe langs veggene er der vindauge med småruta farga glas i blyinnfatning.
Prefabrikert Christie-kyrkje
Kommunestyret i Sogndal hadde bestemt at det skulle reisast ei kyrkje i åttekant-form på Stedje til erstatning for stavkyrkja. Oppdragsgjevaren sette ein frist, og då byggmeister og kyrkjeteiknar Johannes A. Øvsthus ikkje klarte å halde den, vart han fråteken oppgåva. Etter råd frå sokneprest Dahl i Lærdal vart det sendt førespurnad til arkitekt Christie i Christiania. Han tok på seg oppdraget.
No skulle den gamle, vesle stavkyrkja erstattast med ei som kunne romme mange. Arkitekten og kommunestyret kom fram til at den nye kyrkja skulle ha 700 sitjeplassar og ha same form som den planlagde Borgund kyrkje i Lærdal. Christie både teikna og ordna med at kyrkja vart prefabrikert i hovudstaden. Materialane vart lasta på skuter som kom til Sogn sommaren 1867. I alt kom fem skuter med materialar til både Sogndal, Borgund og Årdal. Etter berre nokre få månader stod den nye, store kyrkja på Stedje ferdig.
Om lag 3000 menneske deltok i den høgtidlege vigslinga den 17. desember 1867. No hadde dei fått ei mykje romslegare, lysare og høgreist kyrkje enn den førre. Men for mange var det ei hending med sterkt islett av sorg. Den gamle stavkyrkja vart i all hovudsak riven fordi soknet trong ny kyrkje, ikkje fordi ho stod til nedfalls. Særleg dei eldre i bygda meinte det ville vore meir på sin plass å utvide gamle-kyrkja.
Orgel i 1911
Stedje kyrkje kosta 6634 spd., ei overskriding på nesten 2000 spd. For å klare dei faste avdraga, vart kvar gard pålagd ein ekstra kyrkjeskatt, medan husmenn og strandsitjarar fekk ein litt mindre del. Glaserte takheller frå Nederland var ein av budsjettpostane som medførte ekstrautgifter.
I 1899 fekk kyrkja vedomnar, og eit tiår seinare vart galleriet bygt ut for å gi plass til det nye orgelet som bygdefolket hadde samla inn pengar til. Det vart teke i bruk i 1911. Etter ei tid vart det sett inn dører på sidene, og der kom ei skikkeleg trapp opp til galleriet. I 1929 fekk kyrkja elektrisk lys og ny lysekrone i koret. På same tida vart bygget kledd innvendig og måla, og det vart sett inn doble vindauge av farga småruter. Alt dette førte til at kyrkja vart lunare og trivelegare.
I samband med jubileumsåret i 1967 vart det igjen utført eit stort oppussingsarbeid innvendig. Då vart også den gamle døypefonten i kleberstein teken i bruk att.
Kunst og inventar
På alteret står to høge lysestakar med tre kuleføter i messing frå 1619. Dei har innskrift som fortel at sokneprest Peder Pedersen Skütte og kona, Anna Nielsdatter, gav desse til Stedje kyrkje. Skütte var sokneprest i Sogndal 1610-1637. I tillegg kjem to låge lysestakar i messing. Nattverdsutstyret er ein kalk i sølv frå 1680, med innskrift; ein disk i sølv, truleg frå før 1700; og ei brødøskje og ei vinmugge i svart keramikk.
Den firkanta døypefonten frå mellomalderen er i kleberstein. Dåpsfatet og dåpsmugga er i messing. Måleriet "Jesus og borna" frå 1979, er laga av H. Brusdal, og heng på nordveggen i koret. Lysekrona i messing er frå 1672. Orgelet frå 1967 har 30 stemmer, og er bygt av Vestlandske Orgelfabrikk.