Mieli oni następnie rozpocząć budowę kościoła, o którym wiemy wyłącznie, że w 1319 roku posiadał aż dziewięć ołtarzy, przez co był budowlą o dosyć pokaźnych rozmiarach, wybudowaną z drewna.
Kamień węgielny pod budowę obecnego kościoła mieli położyć joannici w 1344 roku z inicjatywy arcybiskupa Arnoszta z Pardubic, co wiązało się z wizjami, jakich miał doznać w czasach młodości w Kłodzku, gdzie dorastał. Jak napisał jeden ze współczesnych biografów arcybiskupa Frantiśek Śebek:
Arcybiskup umierając zapisał w swoim testamencie z 1364 roku poważne sumy na cele dalszej budowy. Według niektórych uczonych rozpoczęto budowę od zachodu, co było dosyć ciekawym posunięciem. Prace planowano rozpocząć w drugiej połowie XIV w., jednak zamiary te zaczęto realizować dopiero na początku XV wieku. Zbudowano wtedy wschodnią część świątyni (prezbiterium), kaplicę św. Zygmunta i mury kaplicy św. Anny (obecna Kaplica Zmarłych).