Die ursprünglich frühgotische Kirche wurde im 13. Jahrhundert zusammen mit der Stadt erbaut und kam 1305 unter die Verwaltung des Prämonstratenserordens im nahen Schlägl. In der ersten Hälfte des 16. Jahrhunderts wurde die Kirche im spätgotischen Stil umgebaut. Als erstes wurde der Chor mit einer eingeschossigen Sakristei und einem Beinhaus im Untergeschoss gebaut. Die Arbeiten am Rohbau fanden um 1530 statt, wie die Datierung am Nordostpfeiler belegt. Kurz darauf wurde zwischen Sakristei und Kirchenschiff ein Glockenturm errichtet. Zwischen 1530 und 1540 wurde ein flach gedecktes Kirchenschiff mit steilem Westgiebel fertiggestellt. Die Gesamtbauzeit der Frymburk-Kirche ist sehr unklar und kann nur grob bestimmt werden, da im Gut Rosenberg gewöhnlich Stadtkirchen gleicher Größe innerhalb von 20-30 Jahren gebaut wurden.
