On 30 January 1920 the first HAPAG ship "Hörnum" travelled from Swinemünde to Pillau on behalf of the German Government.
The route subsequently expanded to Memel (Klaipėda) (1927) and Liepāja (1930) in Lithuania and Latvia respectively, and Lübeck-Travemünde (1933) and Kiel (1934) in Schleswig-Holstein.
Due to the increasing distances the original ships were no longer able to meet the requirements of the route and in 1926 the "Preussen" (of Shipping Company Braeunlich) and the Hansestadt Danzig (of North German Lloyd) went into service, followed by "Tannenberg" (of HAPAG) in 1935.
The projected "Marienburg" wasn't finished after the beginning of World War II, but completed in 1950 in Wismar as a reparation for the Soviet Union, later running as „Ленсовет" (Lensoviet) and „Абхазия" (Abchasia) on the Black Sea and ultimately scrapped in 1980 at Barcelona.
The Sea Service East Prussia was abandoned after Germany invaded Poland in 1939.