Paleontological proxy data and cryolithological information from East Siberian Arctic permafrost preserve records of late Quaternary climate and environmental conditions in West Beringia and their variability which results from interglacial-glacial and interstadial-stadial dynamics. A key site for late Pleistocene Ice Complex is situated at the southern coast of Bol’shoy Lyakhovsky Island (Dmitry Laptev Strait) where coastal outcrops expose frozen sediments, ground ice, and fossil remains. A 15 m long sequence of Ice Complex permafrost accumulated continuously between >49 and 29 kyr BP in an ice-wedge polygon reflecting the palaeoenvironmental history from the end of the MIS4 stadial to the end of the MIS3 interstadial (Oyogos and Molotkov horizons of the Oyogosskaya Suite). The late MIS4 stadial (>49 kyr BP) record shows a quickly developing polygon tundra while harsh cold and dry summers are reflected by sparse grass-sedge tundra-steppe and high amounts of redeposited conifers. During the early MIS3 interstadial (>49 to 48 kyr BP) pollen records show higher Artemisia percentages within a grass-sedge tundra-steppe vegetation that supported dry conditions. The MIS3 interstadial optimum between 48 and 38 kyr BP promoted low-centered polygon tundra with shallow water in polygon centers. Moister conditions in the landscape than during the previous late MIS4 stadial are assumed while the general summer climate conditions likely remained dry, but slightly warmer as reflected by higher Salix abundances. Warmer summer air temperatures and moister conditions on landscape scale during the MIS3 optimum are revealed mainly by Salix and green algae findings in the palynological tundra-steppe records. A late MIS3 cooling trend in summer air temperatures between 38 and 29 kyr BP can be deduced from disappearing Salix pollen. The stable water isotope composition of an ice wedge (mean values of -31‰ in δ18O and -243‰ in δD) point to stable cold winter conditions. Changes in the accumulation conditions are indicated at the end of the MIS3 in transition to the MIS2. The Last Glacial Maximum (LGM) period has been rather poorly represented in East Siberian permafrost records. However, present pollen, sediment, and ground-ice stable water isotope data obtained from coastal exposures on Bol’shoy Lyakhovsky Island mirror the coldest conditions during the MIS 2 stadial (Sartan horizon of the Yanskaya Suite) period between about 26 and 22 kyr BP. The pollen record reveals a cold tundra-steppe vegetation with characteristic predominance of grass pollen over sedge pollen while the stable isotope ice-wedge data indicate extremely cold winter temperatures with mean values of -37 ‰ in δ18O and -290 ‰ in δD. By the use of combined cryolithological, sedimentological, geochemical, geochronological, and palaeontological proxy data, stadial-interstadial environmental variability in arctic West Beringia was elucidated at millennial resolution.