The geologic deposits of the Southeastern United States of America are missing nearly 350-million-years of rocks, sediments, and fossils. This gap defines the Fall Line nonconformity where Upper Ordovician consolidated rocks are directly overlain by Upper Cretaceous unconsolidated sediments of the Atlantic Coastal Plain Province. Here we begin to fill in the missing geologic record by reporting the discovery of fossils of lower-to-middle Paleozoic tabulate corals (Syringophyllidae) in angular, quartz-rich, ferruginous sandstones that crop out in the Carolina Sandhills Physiographic Province that forms the updip margin of the Atlantic Coastal Plain Province near the Fall Line. These fossils of extinct tabulate corals are the first evidence that Paleozoic (Upper Ordovician–Lower Silurian) sandstones crop out amidst the mostly Mesozoic-to-Cenozoic deposits of the Atlantic Coastal Plain Province of the United States of America. This discovery of Paleozoic fossils and strata in a region in which they were previously entirely unknown offers a more complete insight into the geologic history of the Southern Appalachian Mountains Region, Carolina Sandhills and updip margin of the Atlantic Coastal Plain Province and extends the previously identified range of Syringophyllidae in North America.