“We were off the coast of the islet of Skantzoura. “Easy does it… there it is,” shouted Captain Spyros as he watched the net rise from the water, sagging under the weight of a massive lobster glowing like copper in the morning light. Now that was a dawn I’ll remember for many years to come. The scent of cedar and lentisk hung in the air as I watched the ascending sun cast its glow over the islands that form the National Marine Park of Alonissos and the Northern Sporades. A boat ride out here is an experience you’ll never forget, and that was just the beginning of our travels around this island cluster.

We spent the rest of that day in the sea off the islet of Peristera, and in the evening we disembarked at Steni Vala on Alonissos and supped on a heady fish stew made with Captain Spyros’ catch while talking of shipwrecks and pirates. With so many islands both big and small, this area was a marauder’s paradise. Long before those cutthroats ruled the seas around here, however, other ships disappeared in these waters. After dinner, I browsed through a book of photographs of the legendary ancient wreck of Peristera, discovered in a cove just across the water from where we were sitting, with its load of thousands of ancient amphorae strewn about on the seabed.

We got some fresh supplies from Steni Vala and set sail again, our boat cutting across the placid waters west of Peristera. We passed the popular bay of Vasilikos and dropped anchor a bit further to the north, right beside the site of another shipwreck, a half-sunken motor ship. I donned my mask, flippers and neoprene vest, and swam down to explore the rusting giant, which was seemingly encased in schools of silver anchovies and other small colorful fish. A Moray eel stared at me through a darkened porthole, and small sea bream gathered right above the green sea grass growing just off the tip of the smashed keel.

There are so many ancient, medieval and modern shipwrecks scattered across this area, which was known in the Middle Ages as “Hiliadromia,” or “Thousand Crossings” after the myriad sea routes that converged here. Below the surface, the sea is like a vast underwater museum, sealed in silence.

“Look… there… there,” shouted the captain back on the deck, passing his binoculars and pointing to a seal swimming off the northeastern coast of Alonissos, at Gregali Bay. It turned its silver head to look at us with apparent curiosity. Seals can be spotted all over the place now, even near the port at Patitiri. As the sirocco filled our sails, we headed towards a horizon dotted with small masses of land shimmering in the hot midday sun.

Off the coast of Lechousa, we spotted some small wooden fishing caiques, and then some dolphins hunting a school of sardines. We reached the Bay of Aghios Petros in Kyra Panaghia and stopped for a swim in front of the islet of Melissa, the seabed of white sand lending the sea an irresistible azure hue. We dived in with great glee and had our swim as the crew of a small motorized fishing boat cleaned their nets nearby, a catch of scorpion fish glistening red and black in a wooden crate on the deck. The smell of saltwater mingled with the scent of wet seaweed. We invited the captain over for a coffee and he told us of a cave in Planitis Bay.

Our next stop was at the bay below the Monastery of Panaghia, and this time we went ashore to visit the holy building that has stood on this fragrant holly-oak-studded promontory since AD 993. As we set off again, we heard the cheerful shouts of a group of Germans snorkeling around their boat. They had spotted a massive cauldron in the shallows, a remnant from the wreck of a Turkish steamer that went down with its cargo sometime in the early 20th century.

The sun by now was scorching, casting a haze across the sky so that we could barely make out the ash-grey dome of the church on the islet of Pappous. A southwesterly wind hit our sails as we approached Gioura, where we saw a fisherman pulling up his lines; he held up a large porgy for us to see. Boats aren’t allowed to approach Gioura any closer than half a mile, so we admired its cliffs and dark waters from afar, spotting a few wild goats in the shadows of the rocks.

We headed northeast towards the growing black dot of Piperi, the heart of the marine park and an ideal habitat for the protected Mediterranean monk seal (Monachus monachus). Piperi is also off limits, so we headed north to Psathoura for a stop and an afternoon swim at the white sand cove of Mandraki on its southern coast. I geared up again and swam out to the western coast, where the sea has that clear Caribbean look, thanks to the light-colored cliffs that come crashing down into the water. Small schools of golden-striped cow bream swam in front of my mask and further in, where pebbles and purple sea urchins gave way to meadows of Posidonia seagrass, I spotted a pair of orange ocellated wrasses with that telltale sapphire spot at the base of their tail. They were so beautiful, I almost forgot to go back up for air.

A bit later, we were treated to glasses of chilled Malagouzia, a white wine from Greece, and some tuna caught earlier by the passengers of a luxury yacht that now drew up beside us. Sipping and nibbling, we looked out across the northern Aegean stretching from Limnos to Mount Athos, and then over at the Psathoura Lighthouse. Sailors warn against being caught in a windstorm here – apparently, they sweep down from Halkidiki – but our day at sea was, thankfully, calm and clear.

We returned to Kyra Panaghia before nightfall to spend the night in Planitis Bay, one of the safest anchorage spots in the Mediterranean. As the sky turned pink, flocks of seagulls and Eleonora’s falcons swooped above the islet of Sfika.

We put on our waterproofs to protect us from the humidity and started reading about the pirates who for centuries had sought shelter, just as we were doing now, in this very spot. We made plans to take the dinghy out the following morning, for a swim at the small white sand beach on the other side of Sfika, rumored to be the loveliest beach on these small uninhabited islets known as the Erimonisa, or “Deserted Islands.”