Pôvodná stavba historického rímskokatolíckeho kostola podľa archívnych záznamov pochádza z roku 1297.

Farnosť bola v tom čase súčasťou Jágerskej diecézy. Svedčí o tom aj jeden z najstarších dokumentov viažucich sa k histórii Košickej Novej Vsi a objektu kostola sv. Ladislava. Ide o zápis z kanonickej vizitácie, ktorú v roku 1771 vykonal jágerský biskup Karol Eszterházy. Píše sa v ňom: „Na usadlosti Košická Nová Ves (Cassa – Ujfalu) je farský kostol. Ten bol postavený z kameňov dozaista v roku 1297. Oprava sa predviedla v roku 1510, kto však postavil tento kostol, sa nevie. Kostol bol zasvätený sv. Ladislavovi, uhorskému kráľovi. V roku 1750 bol znova opravený…”
Ďalším dokumentom je súpis desiatkov, ktoré vyberal pápežský legát Ruffinus pápeža Jána XXII. z Avignonu v rokoch 1317 až 1337: „Tiež Mikuláš z Novej Vsi (Nicolaus de Nova Villa) z tretej čiastky kostola má zaplatiť 6 grošov…”

Priestor okolo kostola slúžil v minulosti aj ako cintorín, bol ohradený múrom, dnes však po ňom niet stopy. Pod kostolom bola kedysi hrobka, tá však spustla počas maďarských povstaní aj s kostolom. Súčasne s kostolom bola založená aj fara, takže Košická Nová Ves už na začiatku 13. storočia mala vlastného farára. Rozsiahle nehnuteľnosti fary ležali v južnom intraviláne obce.

V období reformácie kostol chátral a k rozsiahlej oprave došlo až po jeho opätovnom prevzatí do majetku mesta Košice. K ďalším zaznamenaným opravám došlo až v rokoch 1864 a 1885. Zásadne ho potom prestavali v roku 1925, podľa projektu košického staviteľa Júliusa Wirtha. Časť pôvodného ranogotického presbytéria sa zachovala dodnes. Socha Madony zo začiatku 16. storočia bola dielom prešovského rezbára Jána Weissa a v súčasnosti sa nachádza v múzeu v Budapešti. Sochu sv. Ladislava vytvoril v roku 1948 F. Cibala. Figurálne nástenné maľby sú dielom Viktora Smolku. Obraz sv. Jána Nepomuckého, v bočnej lodi, pochádza z polovice 18. storočia. Je to olejomaľba v pôvodnom rokokovom ráme.

Po úprave vo svätyni a osadení pevného oltára bol kostol slávnostne konsekrovaný Mons. Alojzom Tkáčom, košickým arcibiskupom – metropolitom 5.8.2001.