Несмотря на то, что пиратство становилось делом государственным, Вальдемар IV попытался вести с ним борьбу, установив твердый контроль в проливе Эресунн, однако взимание пошлин с проходящих этим проливом судов вылилось в открытый конфликт с Ганзой. В 1367 году семьдесят семь ганзейских городов объявили Дании войну, закончившуюся 24 мая 1370 года Штральзундским миром. Ганза не только получила во владение на пятнадцать лет четыре города на восточном берегу Эресунна, но и право вето на избрание датских королей.
В 1376 году с согласия Ганзы регентшей Дании при малолетнем Олаве стала его мать Маргарита - дочь Вальдемара IV и жена норвежского короля Хакона VI. Не желая зависеть от прихотей ганзейских купцов, она очень скоро стала нанимать на службу пиратов западной части Балтики и натравливать их на ганзейские корабли и центры. Больше других начали страдать вендские города Висмар, Любек, Росток и Штральзунд. Дело кончилось тем, что они тоже вошли в соглашение с пиратами, после чего началась борьба за выживание - кто кого. Росток и Висмар быстро обогащались, особенно после того как предоставили пиратам свои порты и рынки, где те преспокойно сбывали награбленное. Не пренебрегали услугами рыцарей моря и другие ганзейские города, а вскоре в пиратских войнах принял участие шведский король Альбрехт Мекленбургский.
После двух лет непрерывных грабежей всеми всех определилось наконец соотношение сил. Ганза запросила пощады, предложив Маргарите мир. Он был заключен в 1382 году, но разбойничью карусель, закрученную Маргаритой, не могла уже остановить и она сама, хотя большинство пиратов после заключения мира покинуло западно-балтийские воды, перебазировавшись в район Гданьского залива. Самые стойкие остались. Для борьбы с ними Маргарита вступила в соглашение с Тевтонским орденом, и они совместно учредили по примеру венецианцев нечто вроде морской полиции. Во главе объединенного флота из четырнадцати кораблей был поставлен сконский (по другим данным - штральзундский) горожанин Вульфлам. Но ему приходилось гоняться за собственной тенью.
Весной 1389 года Альбрехт был захвачен в плен Маргаритой, ставшей, таким образом, еще и королевой Швеции, а единственный верный королю ганзейский город Стокгольм был осажден датчанами, и его падение грозило отменой привилегий ганзейских купцов.
Ганза обратила свои взоры на Готланд, чрезвычайно удобно расположенный по отношению к столице Швеции. И не просчиталась. Уроженец готландского города Висби шведский полуаристократ-полупират и приближенный готландского правителя Эрика, сына Альбрехта, Свейн Стуре предложил ганзейцам свои услуги, с благодарностью ими принятые. Своей базой Стуре сделал родной город, где с незапамятных времен местные корабелы охотно ремонтировали пиратские суда, а жители принимали на хранение добычу. В этом-то древнейшем пиратском гнезде Балтики Свейн Стуре с благословения купцов Висмара и Ростока провозгласил образование витальерского братства. Как Ганза в свое время заменила викингов в балтийской торговле, так в балтийском разбое на смену им пришли витальеры. Пришли с согласия и по поручению Ганзы. Девять ганзейских городов и мекленбургский герцог Иоганн едва успевали подписывать витальерам каперские свидетельства от имени Альбрехта.
Сложившаяся ситуация диктовала витальерам два пути помощи Стокгольму - или разгромить датский флот, или помочь шведам выдержать осаду. Стуре избрал второй и на своих легких маневренных суденышках, раз за разом обманывая бдительность датчан, взялся за подвоз продовольствия в осажденный город. От шведского слова viktualier, означающего «продовольствие», и произошел термин «витальеры». В 1392 году, пишет любекский хронист Детмар, «собрался неукротимый народ из разных мест - городские заправилы, горожане из многих городов, ремесленники и крестьяне - и назвали себя братьями-витальерами. Они заявили, что хотят выступить против королевы Дании, чтобы помочь королю Швеции, который был ею пленен».
Девиз всеобщего равенства и братства, под которым они шли в бой, снискал им симпатии простонародья, и не без его помощи витальерам удавалось иногда овладеть довольно крупными и хорошо укрепленными городами - такими, как Висмар или Берген.
Сожжение в Бергене торгового представительства Ганзы и постоянные нападения на ганзейские суда поставили, однако, это братство вне закона, и с 1392 года оно стало чисто пиратским. Детмар отмечает, что в эти годы «к сожалению, они наводили страх на всем море и на всех купцов: они грабили и своих, и чужих, и от этого сельдь очень подорожала». Висмар и Росток закрыли перед витальерами свои порты и рынки и вскоре первыми познали ярость и жестокость недавних союзников. Но и другим городам доставалось не меньше.