A templom létrejötte Mária Terézia nevéhez fűződik. A legenda szerint a királynő Bécsből Buda felé tartott, amikor hintója megsüllyedt az ingoványos mosoni talajon, és csak a polgárok segítségével tudott tovább utazni.
Mária Terézia ígéretet tett, hogy hálából erre a helyre templomot építtet, ha a területet feltöltik és olyan szilárd alapot hoznak létre, amely a templom építését lehetővé teszi. A szorgalmas mosoni polgárok elvégezték azt a munkát, amelyet a királynő kért. Ígéretét betartotta az uralkodónő és az Ő anyagi támogatásából felépült a templom, amelynek védőszentje Nepomuki Szent János.
Az első templom a Királydombon állt a mai Szent János kápolna helyén. Centrális fekvésű volt a vár főutcáján. A templomnak kő tornya és fa kórusa volt. 1529-1673 között a törökök által súlyos károkat szenvedett. 1753-ra a hívek növekvő száma miatt kicsinek bizonyult.
A mai templom 1757-ben épült késő barokk stílusban, alacsony gúla alakú toronysisakkal. Műemlék jellegű építmény, a múlt század végi átépítés folytán neobarokk elemekkel is gazdagodott. A főoltár barokk stílusú, 1880-ban építették újjá.