Legenda głosi, że w miejscu, w którym dziś wznosi się kościół św. Sebastiana, znajdowała się pogańska świątynia poświęcona bogince Ledzie. Płonął tu wieczny ogień, nad którym nieustannie czuwały kapłanki-dziewice. Każda z nich pełniła służbę przez rok, nie mogąc odejść od ognia, ani zmyć brudzącej je sadzy. Po upływie roku, wiosną, obyczaj nakazywał im znaleźć swoje następczynie. Chodziły więc po wsi i zaglądały do domów, wyszukując chowające się przed nimi dziewczęta. Wybranki, jeśli nie było ich stać na wykupienie się, musiały odsłużyć rok w służbie bogini. Dziś pamiątką po pogańskim chramie jest nazwa okolicy, w której się znajdował – Lednica. To także obyczaj wielkanocny – Siuda Baba – obchodzony jedynie w Lednicy, odwołujący się do dawnej tradycji poszukiwania przez kapłanki swoich następczyń. Dziś Siudą Babę, czarną od sadzy, przedstawia usmolony mężczyzna przebrany za niechlujną kobietę, z naszyjnikiem z ziemniaków lub kasztanów i batem w ręku. Chodzi on w towarzystwie kominiarza i Krakowiaków w ludowych strojach po domach, mażąc sadzą ręce i twarze domowników. Jednak uwolnienie się od jego obecności jest obecnie znacznie łatwiejsze – wystarczy wykup w postaci drobnego datku albo... buziaka złożonego na usmolonym obliczu.

Z dziejów kościoła pw. św. Sebastiana

Z powstaniem kościoła św. Sebastiana wiążą się dramatyczne wydarzenia. Otóż w połowie XVI wieku Wieliczkę spustoszyła epidemia cholery. Zmarłych grzebano na oddalonym od miasta cmentarzu na Wzgórzu Lednickim. Gdy żadne środki oddalenia zarazy nie pomagały, zrozpaczeni ludzie złożyli ślubowanie, że jeśli uda się wstrzymać epidemię, zbudują kościół jako wotum wdzięczności. I tak się stało. Budowa świątyni, blisko miejsca, gdzie pochowano zmarłych na cholerę wieliczan, rozpoczęła się w roku 1581. Rok później objął Lednicę w dzierżawę żupnik krakowski Sebastian Lubomirski, który dokończył budowy. Patronem kościoła został św. Sebastian, prawdopodobnie dla uczczenia pamięci fundatora. Konsekracji dokonał 29 czerwca 1598 roku kardynał Jerzy Radziwiłł. Początkowo kościółek był bardzo niewielki, zbudowany na planie kwadratu, i służył jako kościół filialny parafii w Wieliczce. Modlili się w nim mieszkańcy okolicznych wsi: Lednicy, Rożnowej, Kłosowa, Sierczy, a także wieliccy górnicy. Skromne wyposażenie świątyni wzbogacało się z upływem czasu: w roku 1744 zamontowano wykonane przez cystersa  Eliasza Wykuszewskiego organy i zbudowano sygnaturkę z latarnią, zaś jubileusz 200-lecia konsekracji uświetniony został rozbudową kościoła i fundacją trzech ołtarzy. W ołtarzu głównym umieszczony został obraz patrona świątyni, św. Sebastiana, zaś w bocznych – krucyfiks i obraz Matki Bożej pędzla Floriana Cynka. W tym też czasie papież Pius VI udzielił odpustu zupełnego na dzień 20 stycznia, czyli patrona kościoła. 

Rozbudowa przeprowadzona pod koniec XVIII wieku bardzo się przydała, gdyż po pierwszym rozbiorze Polski, gdy Wieliczka znalazła się pod zaborem austriackim, wiekowy, parafialny kościół pw. św. Klemensa został rozebrany z powodu niedających się naprawić szkód górniczych. Niedługo później kościółek pw. św. Sebastiana wystawiony został przez rząd austriacki na licytację, na której zakupiło go miasto Wieliczka, za cenę 271 złotych reńskich i 58,5 krajcarów. W licytacji wzięli udział także protestanci, którzy chcieli zamienić świątynię na zbór ewangelicki. Prawdopodobnie właśnie wtedy do kościółka przeniesiono parafię, a także część sprzętów z rozebranego kościoła pw. św. Klemensa. Jednak szybko rozpoczęto budowę nowej świątyni parafialnej, a drewniany kościół popadł na sto lat w zapomnienie, do tego stopnia, że przez jakiś czas pełnił funkcję austriackiego magazynu.Kiedy jednak zbliżała się trzechsetna rocznica konsekracji, Wieliczanie postanowili gruntownie odnowić zapomniany kościółek, będący wówczas najstarszą wielicką świątynią. Specjalnie powołany Komitet Restauracji Kościoła, na którego czele stanął Antoni Jaglarz i Adolf Scheuringer, Kasjer Magistratu miasta Wieliczki, zajął się zbieraniem funduszy na ten cel. Po zakończeniu najpilniejszych prac remontowych, w 1906 roku, przyszedł czas na zajęcie się wnętrzem świątyni. Wybór Komitetu padł na Włodzimierza Tetmajera z podkrakowskich Bronowic, słynnego malarza, uwiecznionego w Weselu Wyspiańskiego jako Gospodarz, przyrodniego brata jednego z najsłynniejszych poetów okresu Młodej Polski, Kazimierza Przerwy-Tetmajera. Tetmajer szybko zabrał się do pracy i w ciągu dziewięciu tygodni, przy pomocy Józefa Mikulskiego z Wieliczki, kościół upiększony został imponującą polichromią. Artysta wykonał nie tylko polichromię, lecz także odnowił wymagający renowacji obraz z ołtarza głównego oraz dwa obrazy z XVI wieku: Matki Bożej ze śś. Sebastianem i Rochem oraz śś. Mikołaja, Andrzeja i Katarzyny. Jak zapisał później, przy życzliwym staraniu obywatelstwa wszystkiego pomalował kościół ten starożytny, na lepszych czasów Ojczyzny pamiątkę. Po wykonaniu robót tenże artysta malarz, który w tymże czasie zarazem i obywatelskie obowiązki w powiecie krakowskim wykonywał, poodnawiał niektóre zniszczone ręką nieumiejętną ołtarze i kościół do porządku przyprowadzić się starał. W dowód wdzięczności Tetmajer, który najprawdopodobniej wszystkie te prace wykonał bezinteresownie i bez wynagrodzenia, otrzymał od społeczności Wieliczki srebrny pucharek z inskrypcją dziękczynną, który znajduje się obecnie w Muzeum Żup Krakowskich. Uroczystego poświęcenia odnowionej świątyni dokonał  29 września 1906 roku sufragan krakowski biskup Anatol Nowak. Warto wspomnieć, że do uświetnienia kościoła przyczynił się także Stanisław Matejko, bratanek Jana Matejki, który zaprojektował pięknie harmonizujące z wystrojem wnętrza witraże.

Dziś kościółek pw. św. Sebastiana i jego otoczenie to jeden z najbardziej malowniczych zakątków Wieliczki, a którym kard. Karol Wojtyła powiedział niegdyś: Cóż za urocze miejsce! Od 1981 roku sprawowany jest tu stały rektorat. Z okazji jubileuszu 400-lecia konsekracji kościoła wyremontowano konstrukcję dachową, odnowiono ołtarz główny, organy oraz XVI-wieczne obrazy, które obecnie znajdują się w krakowskim Muzeum Archidiecezjalnym. Zamontowano także dwa nowe dzwony, wykonano iluminację i parking. W 2000 roku przy kościele stanął Pomnik Tysiąclecia – wotum dziękczynne dla uczczenia dwudziestu wieków chrześcijaństwa – na którym wykuty jest cytat z Księgi Psalmów: Moja Skała niech będzie błogosławiona, niech będzie wywyższony Bóg, Mój Zbawca! Świątynia znalazła się na Szlaku Architektury Drewnianej, uznana została także za zabytek klasy zerowej.