Die Legendenbildung über Klaus Störtebeker und seine Entourage setzte früh ein. Nahezu alles, was mit den historischen Vitalienbrüdern zu tun hat, wurde im deutschsprachigen Raum im Lauf der Zeit auf die Person Störtebeker fokussiert, in der sich solchermaßen ein Geschehen verdichtete, das realiter sowohl räumlich als auch zeitlich wesentlich umfassender, aber auch deutlich zusammenhangloser war, als es in dieser Legende zum Ausdruck kommt. Dabei sind mehrere Erzählungen und Einzelsagen aus verschiedenen norddeutschen Küstenregionen zu einem Sagenstoff zusammengefügt worden, der alle Bereiche des Lebens und der Taten des Seeräubers Störtebeker und seiner Kumpane umfaßt. In den Einzelsagen geht es um deren Schlupfwinkel und Schätze, um Beutezüge, um persönliche Eigenschaften Störtebekers und seiner Gefährten, um die Gegner und Verbündeten und nicht zuletzt – und in vielen Erzählungen ist dies der Kern – um Gefangennahme und Hinrichtung.
Der Hanse-Historiker Karl Koppmann, der sich Ende des 19. Jahrhunderts als erster mit der Störtebeker-Legende wissenschaftlich auseinandergesetzt hat, hat eine Systematisierung dieses in fast fünf Jahrhunderten entstandenen Legendenkomplexes in vier Gruppen vorgenommen. Zur ersten Gruppe zählte er die Überlieferungen über die Herkunft und Verwandtschaftsverhältnisse Störtebekers.
Diese Einzelsagen reichen räumlich von Ostfriesland bis zur Insel Rügen. Mindestens 15 sagenhafte Geburtsorte wurden bisher gezählt. Quellenmäßig nachzuweisen ist allerdings nur die Namensnennung eines Störtebeker in Wismar. Die soziale Herkunft ist ebenso kunterbunt: Sie reicht vom Knecht über einen Bauernsohn bis zum verarmten bzw. deklassierten mecklenburgischen und ostfriesischen Kleinadligen.
Die zweite Gruppe umfaßt die in den Einzelsagen aufgeführten und insgesamt schier unüberschaubaren Schlupfwinkel und Stützpunkte, die es sowohl an der Ostsee- als auch an der Nordseeküste gegeben haben soll. Die meisten liegen in Pommern, Mecklenburg, Holstein und Ostfriesland. Aber auch in Skandinavien, insbesondere auf der Ostseeinsel Gotland, fanden sich der Legende nach solche. In Mecklenburg und Pommern hausten Störtebeker und seine Schar vornehmlich in Höhlen auf der Insel Rügen (am bekanntesten die nach ihm benannte Höhle bei Stubbenkammer) oder in abseits gelegenen „Schlössern“ bzw. „Burgen“. In Holstein und Ostfriesland waren es dagegen vorzugsweise Kirchen und Kirchtürme wie derjenige von Marienhafe in Ostfriesland nahe der Leybucht. Dort endet heutzutage auch die für den Tourismus aufbereitete Störtebekerstraße, die Norddeutschland mit vielen Abzweigungen durchzieht und gewissermaßen den Aktionsradius des Seeräubers an der deutschen Küste markiert.
