At sunrise on the 16th the great fleet left Messina. The "Reale" led the way; the tall galleasses were towed out by the galleys. It took some hours for the whole armada to clear the harbour, then, on the admiral's signal, they set their sails, and with wind and oar steered south-westward across the straits. The first day's voyage was only a few miles. Don Juan was taking the opportunity of reviewing his fleet, and testing his arrangements for its formation. Each captain had his written orders giving his position when under way and in the line of battle. It was in this formation the fleet anchored along the Italian coast beyond Reggio, on a front of five miles.

Next day the fleet rounded Cape Spartivento, the toe of Italy, and after an attempt to continue the voyage on the 19th was forced by bad weather to put back and anchor under shelter of the land for some twenty-four hours.

As the weather improved, Don Juan decided not to coast round the Gulf by Taranto, but to lay his course from Cape Colonna for Cape Santa Maria (the heel of Italy), and then across the opening of the Adriatic to Corfu. A frigate was sent to inform D'Avalos of the change of plans, and the armada, helped by a favouring wind, stood out to sea and for a while lost sight of land.

It was known that the Turkish fleet had concentrated in or near the opening of the Gulf of Corinth. It might also have put to sea, and Don Juan took precautions in view of a possible encounter during his voyage. Cardona, with his seven swift galleys of the vanguard, was directed to keep twenty miles ahead during the daytime, closing in to a distance of only eight miles at sunset, and increasing the interval again at dawn. The three squadrons of the main body appear to have been formed each in line ahead, the leading ships, those of the admirals, at the head of each squadron, with such lateral intervals between the columns that line of battle could be formed, by the ships coming up to right and left of their flagships. Santa Cruz with the reserve acted as a rearguard, and was to assist any vessel that might be in difficulties. The rear ship of each squadron was to display a large lantern at the mast-head after dark. The admiral's ship was distinguished by three large lanterns.

Forty galleys were detached to bring reinforcements of infantry from Taranto and Gallipoli. Four swift galleys under the command of Gil d'Andrada were sent on in advance to obtain information of the Ottoman fleet.

From Cape Santa Maria the course was set for the Ionian Islands. On the morning of 24 September, through the driving rain that accompanied a heavy thunderstorm, the look-outs of the vanguard could distinguish the chain of islands north of Corfu, the islets of Merlera, Fano, and Samothraki, which with the reefs that almost connect them form a natural breakwater. The wind and sea were rising, and the fleet anchored inside the shelter of the islands and reefs. It was not until 26 September that it reached at length the harbour of Corfu. It had taken ten days to complete a passage that the tourist from Messina to Corfu now covers in a single day.

At Corfu the commandant of the fortress had terrible tales to tell of Ulugh Ali's raid on the island, and the horrors that the Turks had perpetrated in the villages, which now presented a scene of ruin and desolation. Gil d'Andrada rejoined the fleet there. He had not seen the Turkish armament, but he had obtained news of it from coasters and fishermen. He estimated from these reports that it was inferior in numbers to the Christian fleet, and he had learned that, as if conscious of its weakness, it had taken shelter well up the Gulf of Corinth, in the Bay of Lepanto. The bay lies eastward of the point where the gulf contracts into a narrow strait between the "Castles of Roumelia" and "the Morea," then held by the Turks. The defences were of such strength that at the time the strait was popularly known as "the Little Dardanelles."[5] It was thought that it would be hopeless for the allied fleet to attempt to force the passage.

Four days were spent in the waters of Corfu, and 4000 troops of the garrison were embarked. Gil d'Andrada's four galleys had again been sent away to reconnoitre the enemy. On 30 September the weather was fine and the wind favourable, so Don Juan led his fleet from Corfu to the Bay of Gomenizza, thirty miles to the south-east, on the coast of Albania. The galeasses guarded the entrance of the bay; the galleys were moored inside it, bow on to the shore, with their guns thus directed towards it. Working parties were landed under their protection to obtain supplies of wood and water. On 2 October some Spaniards engaged in the work were surprised and made prisoners by Turkish irregulars, Albanian horsemen, who carried them off to the headquarters of Ali Pasha, the Turkish generalissimo, at Lepanto.

Gil d'Andrada rejoined at Gomenizza with news that the Turkish fleet was not more than 200 strong; that pestilence had broken out among its fighting-men, and that many of the galleys were undermanned. This encouraged Don Juan to attempt an attack upon it as it lay in the gulf.