В 1655 г. маркграфство Бранденбург, будучи вассалом Польши (маркграф Бранденбурга совмещал тогда титул прусского герцога) было вовлечено в войну против Швеции (Вторая Северная война 1655—1660). Война привела курфюрста Фридриха Вильгельма к осознанию важности собственных военно-морских сил, так как отсутствие флота в 1656 делало порты Пруссии Пиллау и Мемель открытыми для вторжения шведов. Первая попытка создать свой флот, однако, ограничилась маленькой флотилией Балтийского моря, собранной в 1656 в Пиллау и Мемеле и имевшая в составе всего 3 корабля с 34 пушками в сумме.

Началом флотилии послужил шведский корабль Förgyllda Lejonet, севший на мель у берегов Пруссии в октябре 1655 года. Корабль, водоизмещением в 100-150 т. был построен за год до этого, предположительно в Стокгольме. В следующем году он был снят, отремонтирован, переименован в Clevescher Lindenbaum (существует вариант написания Clevischer Lindenbaum) и принят в казну в ранге фрегата с 10 пушками. В те времена термином "фрегат" обозначались любые быстроходные корабли, вооружение и размеры которых не позволяли им становиться в линию баталии. Судя по размерам и вооружению, Clevescher Lindenbaum  скорее всего был шнявой.

Происхождение названия корабля (Липа из Клеве) не совсем ясно. Известно, что после войны за клевское наследство 1609—1614 гг., в которой участвовал Бранденбург, спор не был окончательно решён до 1666 г.

В 1657 году, воспользовавшись тяжелым положением Польши в войнах со Швецией, Россией и запорожскими казаками, Бранденбург добился подписания Велявско-Быдгощского трактата с Польшей, по которому герцогство Пруссия становилось независимым и примыкало к Бранденбургу. В этом году к первому кораблю прибавился купленный в Кёнигсберге 7-пушечный флейт Churfürst von Brandenburg (курфюрст Бранденбургский), вероятно, из за отсутствия других подходящих судов. Корабль, водоизмещением ок. 250-300 т., использовался до конца войны и в 1662 был продан в Кадисе (Испания).

В 1659 году флотилию усилили ещё два корабля, нанятых на год в Курляндии: 30-пушечный корабль (фрегат) Pax и 12-пушечный шлюп Clementia. Со временем флотилия была увеличена до семи крупных кораблей, трёх канонерских шлюпов и двадцати вооруженных лодок, которые успешно использовались против шведских кораблей и укреплений в заливе Фришез-Хафф со стороны Польши. После войны флот был сокращён из за отсутствия денег, и уже в 1662 году в его составе было всего восемь единиц. Есть упоминание, что между 1661 и 1664 гг. существовал корабль Kurprinz (или Churprinz), но не указано ни типа, ни размеров, ни судьбы.

Clevescher Lindenbaum был продан в 1661.