Providing an underutilized source of information for paleoenvironmental reconstructions, birds are rarely used to infer paleoenvironments despite their well-known ecology and extensive Quaternary fossil record. Here, we use the avian fossil record to investigate how Western Palearctic bird assemblages and species ranges have changed across the latter part of the Pleistocene, with focus on the links to climate and the implications for vegetation structure. As a key issue we address the full-glacial presence of trees in Europe north of the Mediterranean region, a widely debated issue with evidence for and against emerging from several research fields and data sources. We compiled and analyzed a database of bird fossil occurrences from archaeological sites throughout the Western Palearctic and spanning the Saalian-Eemian-Weichselian stages, i.e. 190,000-10,000 years BP. In general, cold and dry-adapted species dominated these late Middle Pleistocene and Late Pleistocene fossil assemblages, with clear shifts of northern species southwards during glacials, as well as northwards and westwards shifts of open-vegetation species from the south and east, respectively and downwards shifts of alpine species. A direct link to climate was clear in Northwestern Europe. However, in general, bird assemblages more strongly reflected vegetation changes, underscoring their usefulness for inferring the vegetation structure of past landscapes. Forest-adapted birds were found in continuous high proportions throughout the study period, providing support for the presence of trees north of the Alps, even during full-glacial stages. Furthermore, the results suggest forest-dominated but partially open Eemian landscapes in the Western Palearctic, including the Northwestern European subregion.