The Middle Stone Age (MSA) is associated with early behavioral innovations, expansions of modern humans within and out of Africa, and occasional population bottlenecks. Several innovations in the MSA are seen in an archaeological sequence in the rock shelter Sibudu (South Africa). At ~77,000 years ago, people constructed plant bedding from sedges and other monocotyledons topped with aromatic leaves containing insecticidal and larvicidal chemicals. Beginning at ~73,000 years ago, bedding was burned, presumably for site maintenance. By ~58,000 years ago, bedding construction, burning, and other forms of site use and maintenance intensified, suggesting that settlement strategies changed. Behavioral differences between ~77,000 and 58,000 years ago may coincide with population fluctuations in Africa.