Germany and the USSR come to a negotiated treaty during WWII before the Western Allies land in France. After the failure of the D-day landings Nazi Germany successfully negotiates a peace deal with the US, UK, and the other western Allies (sans France). Leaving a multi-sided cold war.
The Germans in their peace with the Soviets kept the western Ukraine including the Black Sea port of Odessa which becomes the headquarters to the Kriegmarine's Black Sea fleet. The Black Sea Fleet tends to be only above the Med. fleet in getting ships but the battleship Adolf Hitler, the first in the class of the 1960s era battleships, named after the recently deceased leader, is permanently stationed there.
How's that?