Ungefähr in der Mitte des Kaulbergs, oberhalb der Oberen Pfarre, steht das ehemalige Kloster St. Theodor, das die Karmeliten nach Übergabe des Klosters in der Innenstadt an die Jesuiten Ende des 16. Jahrhunderts erhielten.
Der Bau selbst wurde während der Regierungszeit von Bischof Otto I. begonnen (1102 – 1139). Unter Bischof Eberhard II. (1146 – 1170) wandelte man das Kloster aus politischen Gründen in ein Zisterzienserinnenkloster um. Seit dem 14. Jahrhundert zeichnete sich der Niedergang des Klosters ab, während der Reformationszeit wurde es 1554 schließlich aufgelöst. Am 17. März 1589 vollzog sich dann der Umzug der Karmeliten in das leerstehende Gebäude.
Die Zeit der Säkularisation brachte die erneute Auflösung des Klosters im Jahr 1803. Knappe 100 Jahre später, am 2. November 1902 kauften die Karmeliter das Kloster von der Stadt Bamberg zurück. Unter den Nazionalsozialisten wurde vergeblich versucht, das Kloster 1941 erneut aufzulösen. Bevölkerung und Bischof retteten die Karmeliter.
Die Kirche erscheint als Barockbau, jedoch sind große Teile des Mauerwerkes noch mittelalterlicher Herkunft. Die ehemalige Westfassade beherbergt das älteste Kirchenportal Bambergs und dokumentiert die Einordnung als eines der wichtigsten romanischen Zeugnisse der Stadt. Ebenfalls ein Kunstwerk ist die Renaissancefassade im Osten.
Der Kreuzgang liegt etwa 5 m über dem Bodenniveau der Kirche. Der Vorläufer des heutigen Kreuzganges ist wohl schon im 12. Jahrhundert entstanden. Die jetzige Anlage wurde in der zweiten Hälfte des 14. Jahrhunderts vollendet. Schwere Schäden erlitt der Kreuzgang nach der Säkularisation, als wegen des Umbaus die Säulen des Westflügels herausgerissen und zum Großteil verkauft wurden. Nach dem Wiedereinzug der Karmeliten konnte in langjährigen Mühen eine beträchtliche Stückzahl zurückgekauft und wieder eingebaut, bzw. soweit Säulen vermauert waren, freigelegt werden. Im Zuge der letzten großen Restaurierung 1970/72 wurden die im Westflügel fehlenden Säulen durch schmucklose Kopien ersetzt.
