Jednym z najważniejszych zabytków Preszowa jest konkatedra. To najstarszy i jedyny zachowany gotycki budynek sakralny w mieście. Jest to kościół trójnawowy, zwany halowym, jakie rozpowszechnione były głównie na ziemiach niemieckich. W przeszłości był on uważany za jeden z najdoskonalszych przykładów kościołów halowych na terenie dawnych Węgier. Wśród budowli tego typu na Słowacji pod względem wielkości plasuje się tuż za kościołem św. Jakuba w Lewoczy i katedrą św. Marcina w Bratysławie. Początki kościoła sięgają okresu sprzed uzyskania praw miejskich i prawdopodobnie od XIII wieku na jego miejscu stał kościół niemieckich osadników. Budowa katedry rozpoczęła się w 1347 roku, kiedy to królowa Elżbieta Łokietkówna zezwoliła mieszkańcom Preszowa na wydobycie w tym celu kamienia w regionie Szarysza. Kościół sześciokrotnie trawiły pożary, ostatni miał miejsce w 1887 roku. Jako katolicki kościół parafialny służył do 1531 roku, kiedy to większość mieszczan i duchownych przyjęła nauki Lutra. Przez następne 140 lat był kościołem ewangelickim obywateli narodowości niemieckiej. Po zajęciu miasta przez wojska habsburskie w 1671 roku ponownie stał się kościołem katolickim, a podczas powstania, którego przywódcą był Imre Tököli w latach 1682–1686 znów służył ewangelikom. Po raz ostatni kościołem ewangelickim był w czasie powstania Franciszka II Rakoczego w latach 1705–1711. Od tego czasu jest rzymskokatolickim kościołem parafialnym. Pierwotnie kościół posiadał dwanaście gotyckich ołtarzy. Większość z nich została zniszczona w pożarach, a przede wszystkim w rezultacie walk religijnych toczących się podczas powstań antyhabsburskich. Z innych gotyckich przedmiotów w kościele zachowała się nadzwyczaj cenna rzeźba Ukrzyżowanego z pierwszej połowy XIV wieku, rzeźba Chrystusa Cierpiącego dłuta Mistrza Pawła z Lewoczy oraz rzeźba Archanioła Gabriela z XV wieku, która była prezentowana na Wystawie Światowej w Wiedniu w 1873 roku. W 2008 roku kościół parafialny św. Mikołaja został podniesiony do rangi konkatedry.
Z wieży kościoła roztacza się wspaniały widok na centrum Preszowa, dachy średniowiecznych kamienic i szeroką okolicę. Wieża katedry św. Mikołaja w sezonie letnim jest otwarta codziennie, zarówno dla grup zorganizowanych, jak i osób indywidualnych.
