Shulgan-Tash (also known as Kapova) cave located on the western slope of the Ural Mountains (Russia) is the easternmost European cave art monument of late Palaeolithic age. Radiocarbon dates from cultural layers in the cave suggest an age of about 16.3 to 19.6 ka (cal BP), but dates directly on the paintings were not obtained. In order to constrain the age of this art using an independent method, we performed detailed 230Th-U dating of calcite flowstone underlying and overgrowing the paintings at 22 sites in three halls of the cave. The youngest age for the underlying calcite (i.e., the maximum age of the cave art) is 36.4 ± 0.1 ka, and the oldest overlying calcite (constraining the minimum age of the cave art) is 14.5 ± 0.04 ka. The ca. 21.9 ka-long hiatus in calcite deposition during which the paintings were made is attributed to regional permafrost conditions and sub-zero temperatures inside the cave during Marine Isotope Stage (MIS) 2. This is supported by samples of cryogenic cave calcite, which document seven episodes of freezing and thawing of permafrost associated with stadials and interstadials of MIS 3, respectively.