The age of the Vindhyan sedimentary basin in central India is controversial, because geochronology indicating early Proterozoic ages clashes with reports of Cambrian fossils. We present here an integrated paleontologic-geochronologic investigation to resolve this conundrum. New sampling of Lower Vindhyan phosphoritic stromatolitic dolomites from the northern flank of the Vindhyans confirms the presence of fossils most closely resembling those found elsewhere in Cambrian deposits: annulated tubes, embryo-like globules with polygonal surface pattern, and filamentous and coccoidal microbial fabrics similar to Girvanella and Renalcis. None of the fossils, however, can be ascribed to uniquely Cambrian or Ediacaran taxa. Indeed, the embryo-like globules are not interpreted as fossils at all but as former gas bubbles trapped in mucus-rich cyanobacterial mats. Direct dating of the same fossiliferous phosphorite yielded a Pb-Pb isochron of 1,650 +/- 89 (2sigma) million years ago, confirming the Paleoproterozoic age of the fossils. New U-Pb geochronology of zircons from tuffaceous mudrocks in the Lower Vindhyan Porcellanite Formation on the southern flank of the Vindhyans give comparable ages. The Vindhyan phosphorites provide a window of 3-dimensionally preserved Paleoproterozoic fossils resembling filamentous and coccoidal cyanobacteria and filamentous eukaryotic algae, as well as problematic forms. Like Neoproterozoic phosphorites a billion years later, the Vindhyan deposits offer important new insights into the nature and diversity of life, and in particular, the early evolution of multicellular eukaryotes.