Tutejsza parafia utworzona została niewątpliwie w XIII w., jednak dokładna data budowy kościoła nie jest pewna. Jan Długosz podawał, iż został on ufundowany w 1203 r. przez biskupa krakowskiego, Fulkę, zwanego też Pełką; jednak część badaczy, nie zgadzając się z wielkim kronikarzem, przesuwa datę budowy na lata 20-te XIII w., a nawet na drugą jego połowę.
Kościół Podwyższenia Krzyża Świętego i św. Mikołaja reprezentuje w swej architekturze przejściową formę między stylem romańskim a gotykiem - generalnie można go uznać za wczesnogotycki. Na bryłę kościoła składa się kamienna nawa łącząca się z ceglanym prezbiterium oraz kamienna wieża i przedsionek. Prezbiterium, będące najstarszą częścią świątyni, posiada prostokątne zamknięcie, które wieńczy trójkątny szczyt z okrągłym okienkiem. Trzy okna ściany wschodniej zamyka łagodny, ostry łuk. Wieża o grubych murach, na której zawieszone są dzwony, zwieńczona jest obecnie barokowym hełmem z podwójną glorietą. Dwuprzęsłowe wnętrze prezbiterium wieńczy sklepienie krzyżowo-żebrowe. Nawę przykrywa drewniany, otynkowany strop, ozdobiony polichromią. Przedstawia ona ukoronowanie Najświętszej Marii Panny oraz czterech ewangelistów. Empora wsparta jest na czterech drewnianych słupach oraz dwóch przyściennych kolumnach z kamienia.
We wnętrzu znajduje się wyposażenie przeważnie barokowe i rokokowe, na które składa się pięć ołtarzy, a także stalle, ambona oraz kamienna chrzcielnica. W nawie znajduje się nagrobek żyjącego w XVIII w. biskupa krakowskiego Kajetana Ignacego Sołtyka.
Ciekawostką jest, że na strychu kościoła Podwyższenia Krzyża Świętego i św. Mikołaja znajduje się największa w Polsce kolonia nietoperza, nocka orzęsionego.