V centre obce sa nachádza pôvodne románsko-gotický rímskokatolícky kostol Všetkých svätých. Jeho najstaršie časti pochádzajú z druhej polovice 13. storočia. Pôvodný architektonický charakter si však nezachoval. V 18. storočí bol barokizovaný a baroko s klasicizmom tu dnes prevládajú.

Pamiatkový úrad v súpise nehnuteľných kultúrnych pamiatok uvádza dobu vzniku kostola v päťdesiatych rokoch 13. storočia. Ide zrejme o chybu, pretože povolenie na výstavbu kostola v Letanovciach vydal kráľ Ladislav IV. až v roku 1280. Povolenie získal rod Zéckyovcov s odôvodnením, že obec môže mať vlastný kostol, keďže najbližší v Spišskom Štvrtku je jednu míľu ďaleko. Na mieste, kde letanovský kostol začali stavať, stála len kamenná gotická veža. Nevieme však, či mala veža sakrálny charakter (pravdepodobne nie), alebo išlo o stavbu na pozorovanie okolia, aké sa v časoch po ukončení tatárskych vpádov stavali na viacerých miestach. Prvý historický opis kostola prítomnosť veže neuvádza, vedľa kostolnej lode stála samostatná drevená zvonica. Je však pravdepodobné, že časť múrov spomínanej staršej veže tvorí súčasť stavby chrámu.

Najstaršou časťou kostola je Boží hrob, nad ktorým sa zachoval pôvodný románsky portál. V podveží môžete vidieť plastiku Kristus na kríži z 19. storočia. V lodi sa nachádzajú dva obrazy Jozefa Hanulu z konca 19. storočia. V bočnej lodi nad južným vchodom je to olejomaľba Všechsvätých, ktorá bola pôvodne oltárnym obrazom. Veľká olejomaľba Ukrižovaného nie je bežne viditeľná, pretože sa vystavuje len v čase pôstu.

Kostol Všetkých svätých je farský, čiže fara sa nachádza priamo v obci. Býva otvorený len počas bohoslužieb.