It is now well established that many previously obtained radiocarbon dates for the earlier part of the Upper Palaeolithic are problematic, and that archaeological chronologies based on such dates may require revision. In order to help address this problem for the Gravettian of European Russia, eight new radiocarbon dates were obtained on samples of bone from Kostënki 8 Layer II, Kostënki 4 and Borshchëvo 5. The dates for Kostënki 8/II agree with the most ancient date previously obtained for the layer and confirm the dating of the assemblage to ca. 32 000-31 000 calBP, or early Greenland Stadial (GS) 5. The new dates for both Kostënki 4 and Borshchëvo 5 are markedly more ancient than those previously published. They indicate that both sites are ca. 2000 years older than formerly believed, and that both date to ca. 29 500-28 500 calBP, i.e. the very end of GS 5 or Greenland Interstadial (GI) 4. The dates suggest that Kostënki 4 and Borshchëvo 5 are both older than the sites of the Kostënki-Avdeevo Culture, with which they previously seemed to be contemporary. The revised chronology suggests that cold stadial conditions were associated with a relatively low number of archaeological sites in Russia, but also that a notably greater geographical distribution and number of sites may have been associated with GI 3 than with the preceding GI 4. This means that a straightforward correlation between climatic conditions and site numbers should not be postulated based on present evidence.