Background: Quaternary plant ecology in much of the world has historically relied on morphological identification of macro- and microfossils from sediments of small freshwater lakes. Here, we report new protocols that reliably yield DNA sequence data from Holocene plant macrofossils and bulk lake sediment used to infer ecological change. This will allow changes in census populations, estimated from fossils and associated sediment, to be directly associated with population genetic changes. Results: We successfully sequenced DNA from 64 samples (out of 126) comprised of bulk sediment and seeds, leaf fragments, budscales, and samaras extracted from Holocene lake sediments in the western Great Lakes region of North America. Overall, DNA yields were low. However, we were able to reliably amplify samples with as few as 10 copies of a short cpDNA fragment with little detectable PCR inhibition. Our success rate was highest for sediments < 2000 years old, but we were able to successfully amplify DNA from samples up to 4600 years old. DNA sequences matched the taxonomic identity of the macrofossil from which they were extracted 79% of the time. Exceptions suggest that DNA molecules from surrounding nearby sediments may permeate or adhere to macrofossils in sediments. Conclusions: An ability to extract ancient DNA from Holocene sediments potentially allows exciting new insights into the genetic consequences of long-term environmental change. The low DNA copy numbers we found in fossil material and the discovery of multiple sequence variants from single macrofossil extractions highlight the need for careful experimental and laboratory protocols. Further application of these protocols should lead to better understanding of the ecological and evolutionary consequences of environmental change.