O jej istnieniu - jak też istnieniu kościoła - świadczą odnotowane za lata 1346-1358 opłaty świętopietrza, ściągane w wysokości czterech skojców. Istnienie parafii i kościoła potwierdza również informacja przekazana przez Jana Długosza w Liber Beneficiorum: "oppidum Grebov habens in se ecclesiam parochialem muratam, sanctae Catharinae dictam, cuius proprietas ad Serenissum Poloniae Regem pertinent." Najstarsze XVI i XVII-w. wizytacje biskupie podają, że w Grybowie był kościół murowany św. Katarzyny założenia JKM króla Kazimierza. Z powyższych relacji wynika, że prawo patronatu nad kościołem przynależało do króla, zaś fundatorowi miasta Kazimierzowi Wielkiemu zawdzięczano fundację kościoła św. Katarzyny. Wiosną 1908 roku rozpoczęto rozbiórkę starego kościoła (ze względu na zbyt małe rozmiary budowli względem potrzeb wiernych oraz zawilgocenia pojawiające się w kościele), a na jego miejscu rozpoczęto budowę nowego kościoła neogotyckiego.