New reconstructions of changing vegetation patterns in the Mediterranean-Black Sea Corridor since the Last Glacial Maximum are being produced by an improved biomisation scheme that uses both pollen and plant macrofossil data, in conjunction. Changes in fire regimes over the same interval will also be reconstructed using both microscopic and macroscopic charcoal remains. These reconstructions will allow a diagnosis of the interactions between climate, fire and vegetation on millennial timescales, and will also help to clarify the role of coastline and other geomorphic changes, salinity and impacts of human activities in this region. These new data sets are being produced as a result of collaboration between the Palynology Working Group (WG-2) within the IGCP-521 project and the international Palaeovegetation Mapping Project (BIOME 6000). The main objective of this paper is to present the goals of this cooperation, methodology, including limitations and planned improvements, and to show the initial results of some applications.