To understand embryogenesis, it is crucial to elucidate the expression state of each gene in every cell of the organism. This is not feasible at present for most organisms, yet it is conceivable for the nematode C. elegans given that only 1,304 cells occur by the first larval stage. Over thirty years ago, the full cell lineage of C. elegans was deciphered through the pioneering work of John Sulston. While this work defined the ancestry and fate of each cell, the overall underlying gene regulatory networks remain unknown. To assist in this challenge, we previously pioneered a multiplexed single-cell RNA-Seq method called CEL-Seq. Here, we invoke CEL-Seq to define the transcriptome of each cell throughout C. elegans embryogenesis. We collected and processed over two thousand cells from fifty embryos spanning the fertilized egg to the penultimate cell division. We found that cells generally cluster according to their stage and lineage. To decipher the exact identity of each cell we made use of the wealth of previously defined tissue-specific gene expression. The resulting database of gene expression in virtually all cells is a tremendous resource that will be important for developmental biologists, systems biologists, and computational biologists alike. We used the data to explore the general questions of how a cell produces progeny of distinct fates, and how different cells reach the same fate. For this we characterized cell-fate specification at single-cell resolution and report the patterns of similarity in differences for muscle and pharyngeal cells produced by different founder-cell lineages. Our work renders C. elegans the first organism for which the states of all genes are known throughout embryogenesis. While this has been a major undertaking for us, we expect our approach to be routinely adopted for the study of different species and genetic perturbations to further illuminate embryogenesis.