V roce 1938 byla objednána stavba dvou kolesových parníků v Ústí nad Labem. Rozestavěné parníky byly převezeny a dokončeny v Praze. První byl dokončen parník Vltava v roce 1940. Stavba parníku Labe byla dokončena až po válce. Práce byly záměrně prodlužovány, aby parník nemohl být využit pro válečné účely nacistů. Na jaře roku 1949 si parník převzala Československá plavba, ovšem kvůli množství závad byl do provozu zařazen až 14. července 1949. Parník byl poté provozován v Praze.
Kotel parníku byl až do roku 1986 vytápěn uhlím – jednalo se o poslední uhelný parník provozovaný na Vltavě. Tento rok byl parník odstaven pro technickou závadu na kotli. Od tohoto momentu bylo Labe odstaveno u smíchovského břehu, a to až do roku 1997, kdy se parník s ohledem na špatný technický stav potopil.
V roce 1998 byl parník Labe přepraven do Mindenu, kde byl opraven a zároveň vybaven novým jednoplamencovým kotlem. Od roku 2001 pak brázdil vody Vezery pod jmény Wappen von Minden a později Weserstolz.
Na jaře roku 2022 parník Labe převezla Labská plavební společnost. a do mateřského přístavu v Děčíně, kde prošel rozsáhlou opravou a od jara bude jako novinka sezóny 2023 provozován na linkách Labské plavební společnosti.