The study of the Palaeolithic in Senegal has made considerable progress in the last decade and has provided a renewed vision of the behavioral evolution of prehistoric populations in West Africa. The cultural trajectories within the region seem to be highly variable and bear witness to strong behavioral dynamics, the mechanisms of which still need to be better understood. However, the number of reliable, dated, and stratified sites, as well as the palaeoenvironmental data providing a context for populations in their palaeolandscapes, is still scarce. In order to provide new and solid data, we conducted new archaeological survey in the Niokolo-Koba National Park in south-central Senegal, aiming at a preliminary identification of Pleistocene and early Holocene sedimentary deposits. Here, we report an overview of the newly discovered industries found in different contexts. Most of the 27 identified sites show surface and out-of-context assemblages, but other sites are stratified and have all the criteria to justify the development of a long-term archaeological, geochronological, geomorphological, and palaeobotanical project. The Niokolo-Koba National Park, through which the Gambia River flows, is characterized by an abundance of sources of knappable material and by well-preserved sedimentary sequences. Therefore, archaeological research in the Niokolo-Koba National Park has the potential to provide major milestones in our understanding of the evolutionary dynamics at work in West Africa during the early periods of occupation of the region.