Flowering plants possess mechanisms that stimulate positive emotional and social responses in humans. It is difficult to establish when people started to use flowers in public and ceremonial events because of the scarcity of relevant evidence in the archaeological record. We report on uniquely preserved 13,700–11,700-y-old grave linings made of flowers, suggesting that such use began much earlier than previously thought. The only potentially older instance is the questionable use of flowers in the Shanidar IV Neanderthal grave. The earliest cemeteries (ca. 15,000–11,500 y ago) in the Levant are known from Natufian sites in northern Israel, where dozens of burials reflect a wide range of inhumation practices. The newly discovered flower linings were found in four Natufian graves at the burial site of Raqefet Cave, Mt. Carmel, Israel. Large identified plant impressions in the graves include stems of sage and other Lamiaceae (Labiatae; mint family) or Scrophulariaceae (figwort family) species; accompanied by a plethora of phytoliths, they provide the earliest direct evidence now known for such preparation and decoration of graves. Some of the plant species attest to spring burials with a strong emphasis on colorful and aromatic flowers. Cave floor chiseling to accommodate the desired grave location and depth is also evident at the site. Thus, grave preparation was a sophisticated planned process, embedded with social and spiritual meanings reflecting a complex preagricultural society undergoing profound changes at the end of the Pleistocene.