The earliest known archaeological sites North of the Arctic circle are separated from the other Paleolithic sites in Eurasia by vast territories, for which early human occupation is yet to be found. In the Ob River valley, Paleolithic sites are known in the Arctic while the northernmost Late Pleistocene site is located one thousand kilometers south. In the Lower Ob, previous environmental reconstructions supported the idea of a hiatus in occupation, however; new data demonstrate that the development of glaciers and lakes was asynchronous. It suggests that the West Siberian Plain became more suitable for human population than originally thought after the Taz glacial stage. The abundance of landforms and lithic raw material sources suitable for human settlement predicts that the area could have been inhabited during the Late Pleistocene. Hence, we conducted surveys to fully test the potential of this region. We report here the discovery of Pleistocene fauna (including mammoth bones) and possible Paleolithic artefacts in the Ob River Valley, on the slopes near Belogorsk Heights, and the North in the Hashgort Ob area. These findings provide perspectives for further investigation in the lower of the Ob river valley in search for the evidence for human occupation during the Paleolithic.