Working as deckhand and later cattleman, Paul Harris made two return crossings of the Atlantic in 1893. The first, the outward crossing on the 1884-built SS 'Baltimore' of 3730 tons, carried cattle from Philadelphia to Birkenhead and took 14 days. By all accounts, it was rough in almost every way, with primitive conditions, poor food and stormy seas. Once in the Mersey, Harris left the ship and took the opportunity to spend a few days in Liverpool staying at the Sailors' Home before signing on for the return journey.

This time the crossing from Liverpool was on another of W Johnston's ships, the slightly smaller, at 3318 tons, but newer 1890-built SS 'Parkmore'. Both vessels were British owned and Liverpool registered and Harris seems to have found this return voyage more agreeable. He had also enjoyed the chance to do some sightseeing in Liverpool during the stopover. Later that same summer of 1893, he once again signed on, this time as sub-foreman of a gang of cattlemen on the SS 'Michigan' sailing from Baltimore. The 'Michigan' turned out to have much better conditions than his previous ships and proved a much more enjoyable experience.

This time too, there was the added advantage that the freighter's destination was Tilbury on the Thames Estuary and Harris was able to make sightseeing excursions into Central London. However, on this occasion, he only had ten dollars in his pocket so, like one of his heroes Charles Dickens, he learned about the city by walking everywhere. On the return journey, the 'Michigan' put into Swansea where because of a miners strike, the sailing was delayed, enabling Paul Harris to visit various parts of South Wales as well while the ship waited for its cargo. As he said later about these early transatlantic voyages, "The price was high in hardships but my experience gave me an international outlook."

His next visit to Europe was just under two years later, sailing in comparative luxury as a paying passenger. Paul Harris had obtained employment as a buyer of marble and granite for use back in the United States and this gave him the opportunity to travel extensively in Continental Europe, visiting most of Western Europe, except for the Iberian peninsula, over a period of some six months.