Großteils reisten Paul und Leona Kretschmer mit Dampfschiffen, die den Hafen von Triest mit dem Osmanischen Reich, Griechenland und Italien verbanden. Das fehlende Straßennetz führte dazu, dass die Hafenstädte von Inseln wie Lesbos (Mytilini, Plomari, Molyvos) oder Kreta (Chania, Rethymno, Irakleio) am besten über den Seeweg erreichbar waren. Oft kam es zu Verspätungen in den Fahrplänen der Schiffe.
Heutzutage sind diese Schiffsverbindungen eingestellt und durch Inlandsstraßen ersetzt worden.
Eine große Herausforderung, die der Seeweg mit sich brachte, war der Transport vom Schiff zum Hafen, da die Größe der Häfen keine direkte Ausschiffung der Passagiere erlaubte, sondern Barken erforderte.
Kretschmer notierte fast in allen Häfen die Kosten, die die Fährmänner für den Transport zum und vom Schiff verlangten, und die oft zu Streitereien führten.