Wie viele andere Piraten hat auch Klaus Störtebeker seine berufliche Laufbahn als Kaperfahrer begonnen, auf seiten der Mecklenburger Herzöge im Kampf gegen Königin Margarete I. von Dänemark (1387–1412). Das Kapern von Schiffen, also die gewaltsame Aneignung fremder Güter auf hoher See, ist fast so alt wie die Seefahrt selbst. Doch Kapern und Kapern war zweierlei, und so wurde bereits im Römischen Recht zwischen Seeräuberei, das heißt Überfällen auf fremde Schiffe aus reiner Habgier, und der Kaperung im staatlichen Auftrag unterschieden. Ersteres war ein todeswürdiges Verbrechen, letzteres dagegen eine durch Kriegsbrauch und -recht legitimierte Form des Handelskriegs zur See. Wie sein Kumpan Goedeke Michels stammte Klaus Störtebeker wahrscheinlich aus Wismar. Beide sind von 1394 an als Piratenhauptleute in der Ostsee nachweisbar.
Weil der dänische König Waldemar IV. Atterdag (1340–1375) keinen männlichen Erben hinterlassen hatte, war es nach seinem Tod zum offenen Streit zwischen seinen Töchtern gekommen. Ingeborg war mit Herzog Heinrich III. von Mecklenburg, dem Bruder des schwedischen Königs Albrecht, verheiratet, ihre jüngere Schwester Margarete mit dem norwegischen König Haakon VI. Zwar hatte Waldemar noch zu Lebzeiten den Sohn Ingeborgs als seinen Nachfolger ausersehen, doch gelang es Margarete, den dänischen Adel für sich zu gewinnen und ihren fünfjährigen Sohn Olaf am 3. Mai 1376 zum dänischen König wählen zu lassen. Obwohl die Mecklenburger Fraktion diese Entscheidung mit Waffengewalt anfocht, konnte sich Olaf letztlich durchsetzen. In diesen Auseinandersetzungen setzten beide Seiten Kaperschiffe ein, die auch den Seehandel der Hanse erheblich in Mitleidenschaft zogen. 1380 gelang es König Olaf nach dem Tod König Haakons VI. zudem, unter Margaretes Vormundschaft auch die norwegische Krone zu erringen. Doch noch vor Erreichen der Volljährigkeit starb Olaf bereits 1387. Allerdings hatte Königin Margarete ihre Position so geschickt zu sichern gewußt, daß die dänischen und norwegischen Reichsräte sie zur Reichsverweserin bestimmten, statt die nach dem Erbrecht ebenfalls zu Thronansprüchen berechtigten Mecklenburger ins Land zu holen. Als künftigen König wählte Margarete ihren fünfjährigen Großneffen Bogislaw von Pommern-Stolp, der nun den nordischen Namen Erik annahm.
Die Antwort der Mecklenburger war abermals Krieg, der aber alles andere als günstig für sie verlief. 1388 riefen die schwedischen Adligen, die sich mit König Albrecht überworfen hatten, Margarete ins Land und huldigten ihr als Regentin. Damit nicht genug, geriet König Albrecht im Frühjahr 1389 in Gefangenschaft. In dieser prekären Lage verfielen die militärisch unterlegenen Mecklenburger auf die Idee, nach freiwilligen Hilfstruppen zu rufen, um sie auf Kaperfahrt gegen die Dänen und Schweden zu schicken.
Die Mecklenburger waren weder die ersten noch die letzten mittelalterlichen Herrscher, die zu diesem Mittel griffen, denn es war für viele Fürsten der einfachste Weg, rasch zu einer Kriegsflotte zu kommen. Nur die wenigsten mittelalterlichen Staaten waren organisatorisch und finanziell in der Lage, auch in Friedenszeiten Seestreitkräfte zu unterhalten, weshalb man sich im Fall eines Krieges gewöhnlich damit behalf, in aller Eile eine Anzahl Kauffahrer zu Kriegsschiffen umzurüsten. Oftmals griff man auch auf professionelle Hilfe zurück, indem man einfach einige der Piraten in Dienst nahm, die damals die europäischen Gewässer unsicher machten, oder Privatleuten gestattete, auf eigene Kosten und auf eigenes Risiko Jagd auf feindliche Schiffe zu machen. Im Mittelalter wurde das als „Ausliegen“ bezeichnet, später nannte man es Kaperei. Von 1389 an öffneten die Mecklenburger ihre Ostseehäfen allen, die bereit waren, auf eigene Faust mit ihren Schiffen gegen die Handelsschifffahrt der drei nordischen Reiche Krieg zu führen. Damit sollte der Feind geschädigt und die leere Kriegskasse wieder gefüllt werden. Mit dem „Kaperbrief?“ wurden sie ermächtigt, im Auftrag und Namen der Mecklenburger feindliche Handelsschiffe zu kapern; auch ein Teil der Beute wurde ihnen darin zugesichert.
