Gelehrte sprachen die Meinung aus, daß der Sonntagberg ein heidnischer Kultort gewesen sei. Dies ist nicht unglaublich, wenn man die günstige Lage des Berges betrachtet. So erklärt sich auch der Zustrom der Bewohner der Umgebung seit unvordenklicher Zeit und die Erbauung von einer oder zwei Kapellen durch christliche Missionäre wahrscheinlich aus dem nahen Stifte Seitenstetten. Auch sollen Einsiedler die stille Bergeinsamkeit bewohnt haben. Die Äbte von Seitenstetten wandten dem Berge ihre warme Sorge zu. Wie der Abtkatalog des Stiftes berichtet, erbaute 1440 Abt Benedikt I. auf dem Salvatorberg (Heilandsberg) - so hieß damals der Sonntagberg - eine Kapelle.
Die Entstehung der Wallfahrt berichtet die Legende in folgender Weise:
Ein Hirte verlor eines Tage seine Herde und suchte sie mehrere Stunden lang. Endlich war er durch das fruchtlose Umherirren und aus Kummer über die verschwundenen Tiere so müde geworden, daß er nicht mehr weiter konnte. Er sank bei einem rauhen Felsblock zusammen und fiel, nachdem er sich Gott empfohlen, in einen tiefen Schlaf. Der Herr erhörte das Gebet des armen Hirten durch ein freundliches Traumbild, das ihm den Ort zeigte, wo er seine verlaufene Herde wieder finden könnte. Die Freude weckte den schlafenden Mann, und zu seiner Verwunderung sah er neben sich auf dem Felsen ein rundes, weißes Brot liegen, dessen Genuß seine gesunkenen Kärfte belebte. Neugestärkt eilte er nach der im Traume bezeichneten Stelle und fand dort wirklich die verlorene Herde wieder.
Der Hirte erzählte seine ihm wie ein Wunder scheinende Gebetserhörung und Labung durch das gefundene Brot voll dankbarer Freude dem Volke. Diese Begebenheit wurde von diesem als Beweis erkannt, daß der liebe Gott auf jenem Berge besonders verehrt und angebetet werden wolle und ihn auch als eine Zuflucht für bedrängte Christen erwählt habe.
Jener Felsen aber, an dem der ermattete Hirte eingeschlafen und durch das Traumbild von seinem Kummer befreit worden war, erhielt vom Volke den Namen "Zeichen- und Wunderstein". Die Gebetserhörungen nahmen in der Folgezeit stetig zu, wodurch natürlich der Zulauf des gläubigen Volkes immer größer wurde. Die bereits auf dem Berge bestehenden zwei oder, wie es heißt, sogar drei Kapellen genügten nicht mehr, und man mußte daran denken, eine größere Kirche zu erbauen.