Zgodnie z innymi tradycyjnymi przekazami stała tu drewniana kaplica z drugiej połowy X wieku, zbudowana na miejscu zburzonej świątyni pogańskiej.
Faktem historycznym pozostaje natomiast to, że pierwszy murowany kościół w tym miejscu został ufundowany i konsekrowany przez biskupa wrocławskiego Jarosława Piasta, który ukończył dzieło swego poprzednika Żyrosława II. W 1195 roku położono fundamenty, a trzy lata później budowla była już gotowa. Istnienie murowanego kościoła w tym miejscu świadczy o istnieniu sporej osady, gdyż obiekty takie wznoszono wtedy tylko w znaczniejszych miejscowościach, stanowiących większe skupiska ludzi niż zwykła wieś. Ta kamienna romańska świątynia miała służyć nowo utworzonej parafii, obejmującej obszar nazwany później Nowym Miastem (dzisiejsze Śródmieście). W sąsiedniej, starszej od Nysy osadzie, określanej następnie jako Stare Miasto (obecnie okolice ulic Słowackiego i Mariackiej), być może istniał już wówczas kościół św. Jana.
Kościół św. Jakuba i św. Agnieszki został zniszczony wiosną 1241 roku, podczas najazdu tatarskiego. W podziemiach dzisiejszej świątyni można oglądać odkryte po powodzi z 1938 roku pozostałości ław fundamentowych i filarów tej romańskiej budowli.