Die Legende berichtet, dass der Ritter Heinrich von Bülow im August 1383 das Dorf Wilsnack niederbrannte. Die Wilsnacker fanden Zuflucht im benachbarten Groß Lüben. In der Nacht vom 23. August vernahm der Wilsnacker Pfarrer Johannes Cabuez eine Stimme, die ihm befahl, in sein Dorf zurückzukehren und in der zerstörten Kirche die Messe zu lesen. Er tat wie ihm geheißen und entdeckte auf dem Altar, unversehrt von Feuer und Regen, drei blutige Hostien. Für Cabuez und seine Zeitgenossen allerdings waren die roten Flecken auf den Hostien eindeutig das Blut Christi und damit ein großes Heiligtum. Was uns heute wunderlich erscheint, hatte höchst reale Auswirkungen. Aus der Auffindung des „Heiligen Blutes“ 1383 in der verbrannten Wilsnacker Dorfkirche entwickelte sich eine der größten Wallfahrtsbewegungen des späten Mittelalters. Wilsnack kam als bevorzugtes Ziel einer Pilgerreise gleich nach Jerusalem, Rom, Aachen und Santiago de Compostella.
Großes Interesse an den Wallfahrten nach Wilsnack hatten die Bischöfe von Havelberg, denen das Dorf gehörte. Bischof Johann Wöpelitz trieb den raschen Wiederaufbau Wilsnacks voran. Bis etwa 1390 entstand, bereits deutlich größer als die verbrannte Dorfkirche, eine erste Wallfahrtskirche. Ein Teil ihres Turmes sowie Reste der Fundamente sind noch in unserer heutigen Kirche erhalten.
Bald wurde die vorhandene Wallfahrtskirche für den Pilgerstrom zu klein. Ab etwa 1450 begann daher der Neubau der Wallfahrtskirche im Stil der norddeutschen Backsteingotik, zunächst mit der Errichtung eines größeren Chores und eines zweischiffigen Querhauses. Bis 1525 war auch das dreischiffige Langhauses fertig gestellt. Zum Bau der Türme und damit zur Vollendung der Kirche, kam es allerdings nicht mehr.