Гамбургский сенат принял решение в 1401 году окончательно покончить с морскими разбойниками. С этой целью зимой снарядили флот, командование которым поручили членам городского самоуправления Шокке и Ланге. Самым сильным кораблем флота была «Пестрая корова». Это был новый корабль, построенный по особому распоряжению нового гражданина Гамбурга, уроженца Голландии Симона ван Утрехта. «Пестрая корова» и стала флагманским кораблем. Командовал им капитан Херманн Ниенкеркен. Сам Утрехт не принимал участия ни в руководстве операцией, ни в командовании кораблем.
Сколько людей и кораблей участвовало в битве с обеих сторон, осталось неизвестным.
Гамбуржцы подошли к Гельголанду в сильном тумане. Когда они бросили якорь на достаточно далеком расстоянии от кораблей Штертебекера, на воду была спущена шлюпка. В нее сел штурман «Пестрой коровы», подошел к главному кораблю и закрепился у его кормы. Когда шлюпку окликнул вахтенный матрос, переодетый рыбаком, штурман ответил, что он только разогревает еду на огне. Однако на самом деле он расплавил свинец и залил им рулевые соединения корабля. Корабль потерял маневренность, и гамбуржцы смогли взять его на абордаж.
На борту разразилась ожесточенная схватка между корсарами и гамбуржцами, которым никак не удавалось захватить Штертебекера. Всех наседавших на него врагов он валил наземь ударами своего огромного меча. Тогда гамбуржцы пошли на хитрость. Сверху, с реи, они набросили на Штертебекера сетку, которая сковала его движения, и лишь таким образом смогли его схватить.
В подтверждение того, что большое сражение имело место в действительности, свидетельствуют сохранившиеся казначейские счета того времени, в которых наряду с наградой в восемьдесят серебряных марок, предназначенной адмиралу Шокке, упоминаются большие затраты на ремонт судов, получивших повреждения во время этого сражения.
Данные о потерях с обеих сторон остались неизвестными. В хронике упоминается о сорока убитых со стороны противника, но о собственных потерях гамбуржцы не сказали ни слова. Очевидно, после захвата корабля Штертебекера его флоту удалось отойти, ибо, несмотря на то что ликование было огромное, гамбуржцы смогли доставить в свой порт только семьдесят три пленных. Казнь Штертебекера и его товарищей состоялась 20 октября 1401 года на пустынном островке Грасбрук в устье Эльбы.
О том, как проходил суд над ними, об их смерти народ также создал свою версию. Процесс действительно длился почти полгода, это подтверждается казначейскими счетами, хранящимися в гамбургском городском архиве. Каждый обвиняемый получил слово для защиты. По преданию, Штертебекер выступил как защитник бедных и мужественно принял всю вину на себя. Народное сказание говорит об этом так: «Штертебекер был славный малый. Бедным давал, у богатых брал».
Легенда повествует о том, что была исполнена последняя просьба Штертебекера: сохранить жизнь тем из его сообщников, мимо которых он сумеет пробежать после отсечения у него головы. Легенда утверждает, что, будучи уже обезглавленным, Штертебекер пробежал мимо одиннадцати своих соратников. Только когда палач Розенцвейг подставил ему ногу, обезглавленное тело упало на землю.
После смерти Штертебекера возникла песня, которую в различных вариантах пели на немецком побережье Балтийского и Северного морей в течение столетий. От первоначального ее текста до нас дошла только первая строфа. Текст песни, состоящий из двадцати шести строф, датируется 1550 годом. В гамбургском листке «Вольный стрелок» в 1851 году были напечатаны пять строф песни, которая по своей простоте может быть отнесена к одному из сохранившихся народных вариантов песни о Штертебекере: