Die Schwarzmeer-Schiffahrts-GmbH, Nikolajew, wurde am 5.11.1942 gegründet, um "kriegswichtige Verkehrsaufgaben" durchzuführen. Ab 1.4.1943 wurde ihr der "Nachschubdienst für Zwecke der deutschen Kriegsführung im Schwarzen Meer" übertragen. Bis dahin war diese Aufgabe von der Kriegsmarine wahrgenommen worden. Ab 15.6.1943 bereederte sie alle für die Nachschubschiffahrt eingesetzten und nach dem 16.5.1943 zugeführten Schiffe sowie die zu Seeschiffen umgebauten Flußschiffe, so daß sich der Schiffsbestand im Donau-Schwarzmeer-Raum stetig vergrößerte. Im Herbst 1944 wurde die Schwarzmeer-Schiffahrts-GmbH liquidiert und ihre Schiffe wurden von der im November 1942 zum gleichen Zweck geschaffenen Mittelmeer-Reederei übernommen.

Schiffsbestand: Die Reederei verfügte über wenige größere Seeschiffe, z. T. von der Mittelmeer-Reederei übernommen, z. T. Beuteschiffe. Wie bei den anderen "Kriegsreedereien" im Bereich der Gruppe Süd mußte auch ihr Schiffspark durch Zuführung von Kleinschiffsraum aus dem Reich und den okkupierten Gebieten (z.B. aus den Niederlanden) ergänzt werden. Neben Fahrzeugen aus den verbündeten Balkanländern traten ferner in den eroberten sowjetischen Häfen erbeutete und geborgene Kleinfahrzeuge hinzu. Die französischen, belgischen und niederländischen Fracht- und Tankpenichen, die 1943/44 für die 3. Transportflottille zur Donau überführt wurden, wurden ebenfalls von der Schiffahrt-GmbH. bereedert. Auch die in Rumänien in Bau befindlichen Holzschiffe waren für eine Bereederung (in Charter) durch die Schiffahrt-GmbH. vorgesehen.