We describe materials from a new Paleolithic site, discovered in 2020 on the right bank of Mius estuary, near its confl uence with the Taganrog Bay of the Sea of Azov, in the southern outskirts of the village of Nikolaevo-Otradnoye, which is in the Neklinovksky District of the Rostov Region. The clearing of a 10-meter-high river-bluff revealed a complex stratigraphy of subaqueous and subaerial Late and Middle Pleistocene rocks. Horizons with lithics and faunal remains were identifi ed. Cultural remains found in the coastal exposure and in the stratigraphic section belong to the Early and Middle Paleolithic. The early stage in the peopling of the Northeastern Azov and the Lower Don regions is documented by Early Paleolithic artifacts found in the subaqueous deposits of layers 5 and 6 (MIS 9–11, ~420– 270 ka BP). Heavil y waterworn patinated lithics include a core-shaped artifact, variou s types of side-scrapers, a scaled piece, fl akes, and chips. This complex is an informative addition to known complexes from the region, including contemporaneous ones. The most interesting is the Middle Paleolithic industry of layer 4 under the Kamenka (?) soil— layer 3, MIS 7. The toolkit consists of a diagonal side-scraper and a chip found in the section, as well as radial and Levallois cores, various side-scrapers, a par tly bifacial tool, spalls , and chips found in the denudation. Technological and typological criteria (primarily the Levallois technology) and the tentative date of non-waterworn patinated lithics make it possible to attribute them to the Early Middle Paleolithic of the southern Russian Plain. It is concluded that cultural remains of the Early Middle Paleolithic, dating to ~243–191 ka BP, have been found in the region for the fi rst time, fi lling the gap in the local Early Middle Paleolithic sequence. In adjacent regions, similar industries have been known since the late 1900s.