Antages at have ligget syd for St. Sct. Peder Stræde i nærheden af vejgaflen til Sct. Mathias Gade. Her skal der i 1848 være påvist fundamenter fra øst- og sydsiden af en kirke med apsis. Sct. Budolfi sogn nævnes i 1188. Senest i år 1263 var et nonnekloster knyttet til kirken. Klostret blev formentlig nedlagt omkring midten af 1400-tallet. I Christen Erichsøns bog “Viborg Byes Beskrivelse 1727” står der, at også kirken blev nedlagt i 1400-tallet.