New archaeological finds disclose that many of the islands in the vicinity of the Aegean Sea were colonized by modern humans in the Epipaleolithic era, several thousand years before the Neolithic revolution, and some may have experienced earlier maritime colonizations by archaic hominins such as Neanderthals.
This is consistent with evidence of rather short distance Upper Paleolithic maritime colonizations of Australia and Melanesia (it isn't clear if these were separate colonizations or a single event), of the Philippines, of the Andaman Islands, of the island of Formosa (home to Taiwan), of Japan and some of its neighboring islands, and of crossings of the Strait of Gibraltar.
Indeed, while this is earlier than the Neolithic, these dates are still about 30,000 years or more after modern human Cro-Magnons began to inhabit this region.
But, these colonizations seem to have been rare, with their frequency declining as distances grew greater. The sea journey that made modern human colonization of Australia and Melanesia seem likely to have been one time only one way journeys, with only one subsequent known instance of interaction (evidence by the introduction of the Dingo to Australia) between then and the Neolithic, which may also have been a one way journey. Islands, even when accessable by straits easily crossed by boats in the Neolithic and historic eras, are often very distinct genetically from the adjacent mainland (e.g. in the case of Cres Island off the coast of Croatia in Adriatic Sea).
Notably, Madagascar, most of Oceania, and Iceland were not colonized by hominins until the Neolithic era, in the first two cases by Austronesian seafarers, and in the latter case by the Vikings. Similarly, when Tasmania became isolated by water from mainland Australia as sea levels rose, interactions between those societies, who had lost the requisite maritime technology, ceased leading to technological and culture degredation for the remaining people of Tasmania who were less with a population not sufficiently large to maintain its culture. The people of the Andaman Islands also seem to have been isolated from the mainland for many thousands of years.
Consistent long distance maritime travel seems to have been nearly non-existent until roughly the Copper Age (and contemporaneous Austronesian journeys), even though irregular and perhaps one way trips in unusually favorable conditions, or much shorter trips where line of sight navigation is possible, may be as old as the Out of Africa event or older. Alternately, one technology that may be a good fit for regular maritime travel is the development of pottery.
It is a fair assumption that archaic hominins had maritime technologies that were no better than those of Upper Paleolithic modern humans.
To my knowledge, there is no direct archaeological record of pre-Neolithic boats that could have made these crossings at all.
One question that comes to mind, in light of this data, and the indications from genetic evidence that the Epipaleolithic may have seen as much population genetic change in Europe as the Neolithic, is whether there was some sort of behavior modernity shift (perhaps cultural rather than genetic) in the Epipaleolithic on a par with that often attributed to the Upper Paleolithic, even though the existence of a shift to some sort of behavior modernity in the Upper Paleolithic (and even between Neanderthals and modern humans), at all, is seriously disputed by professionals in the field.