The search for sites inhabited by humans of the Late Palaeolithic to Mesolithic period on the coasts of Lithuania is closely related to the coastal and underwater relicts of the Early Holocene and palaeo-watercourses. This article presents the results of coastal, underwater and seismic seabed surveys. The estuaries of the rivers of the Late Mesolithic period could have been at the present seabed level at a depth of 30 m or even deeper. The watercourse sites of the Littorina Sea stage are in shallow coastal waters. At the latitude of Šventoji, Palanga, Klaipėda, Juodkrantė and the area of the Nemunas palaeo-estuary, the seabed was explored with side-scan sonar and by diving. An artefact from the Early Neolithic period has been found in the coastal area next to Klaipėda, and underwater, at a depth of 14.5 m, a relict tree stump has been detected. Two sites at a depth of 10–12 m can be associated with the relict Danė watercourse containing the preserved fragments of relict landscapes. During marine seismic survey, the probable Smeltalė River palaeo-watercourse was detected, and three sites of the former watercourses found to the south of Klaipėda could be the traces of the Dreverna palaeo-river estuary. This area has good prospects as regards the search for Early Mesolithic period settlements. The underwater survey showed no traces of human activity. A further search for the Stone Age sites would be more promising in locations where palaeo-landscapes have survived adjacent to the palaeo-watercourses.