Die Sage von der Erbauung der Felsenkirche zählt wohl zu den bekanntesten Mythen im Bereich zwischen Mosel und Pfalz, Rhein und Saar. Über ihre Entstehungszeit können wir keinerlei Aussagen machen, zumal sie gewiss über einige Generationen zunächst nur mündlich tradiert wurde, bis man sie erstmals niederschrieb. Die bis heute älteste bekannte gedruckte Fassung findet sich in den Rheinischen Provinzial-Blättern von 1836, wobei es sich allerdings um eine literarisch bearbeitete Form handelt. Seit dieser Zeit ist aber der Stoff unzählige Male nacherzählt, dramatisiert und gedruckt worden, sodass es praktisch unmöglich ist, eine authentische Urfassung zu ermitteln.
Im Wesentlichen geht es dabei immer um einen Mord an einem engen Verwandten (Bruder oder Vetter) auf dem alten Schloss in Oberstein (zeitweise “Bosselstein“ genannt), welcher den Anlass zur Erbauung der Kirche gab. Über Ursache und Hergang der Tat sind drei verschiedene Versionen in Umlauf: Einmal ist die Rede von
a) einem tödlichen Pfeilschuss auf einen Vetter,
b) einer Katze, die ein Bruder dem Anderen in den Stiefel steckt und
c) der gemeinsamen Liebe von zwei Brüdern zu dem Burgfräulein Bertha von Lichtenberg.
In den beiden Fassungen b) und c) haben Scherz bzw. Eifersucht jeweils zur Folge, dass ein Bruder den anderen aus dem Fenster der alten Burg wirft, und dieser dann zerschmettert an der Stelle liegen bleibt, wo heute die Felsenkirche steht. Der Bau des Gotteshauses ist in allen drei Versionen die von der Kirche (einem Abt oder einem Bischof) auferlegte Sühne für die ruchlose Tat, wobei der Mörder immer zuvor ruhelos in der Gegend umhergezogen ist bzw. sogar an einem Kreuzzug nach Palästina teilgenommen hat. Der Missetäter soll an der Stelle, an der das unschuldige Opfer gefunden wurde, mit Hammer und Meißel eine Höhlung in den Fels geschlagen, eine Kirche darin errichtet haben und tot zusammengebrochen sein. Angeblich hat man Täter und Opfer danach gemeinsam in dieser Kirche bestattet.