The human uterus is a complex and dynamic organ whose lining grows, remodels, and regenerates every menstrual cycle or upon tissue damage. Here, we applied single-cell RNA sequencing to profile more the 50,000 uterine cells from both the endometrium and myometrium of five healthy premenopausal individuals, and jointly analyzed the data with a previously published dataset from 15 subjects. The resulting normal uterus cell atlas contains more than 167K cells, representing the lymphatic endothelium, blood endothelium, stromal, ciliated epithelium, unciliated epithelium, and immune cell populations. Focused analyses within each major cell type and comparisons with subtype labels from prior studies allowed us to document supporting evidence, resolve naming conflicts, and propose a consensus annotation system of 39 subtypes. We release their gene expression centroids, differentially expressed genes, and messenger Ribonucleic Acid (mRNA) patterns of literature-based markers as a shared community resource. We identify multiple potential progenitor cells: compartment-wide progenitors for each major cell type and potential cross-lineage multipotent stromal progenitors that may replenish the epithelial, stromal, and endothelial compartments. Furthermore, many cell types and subtypes exhibit shifts in cell number and transcriptomes across different phases of the menstrual cycle. Finally, comparisons between premenopausal, postpartum, and postmenopausal samples revealed substantial alterations in tissue composition, particularly in the proportions of stromal, endothelial, and immune cells. The cell taxonomy and molecular markers we report here are expected to inform studies of both basic biology of uterine function and its disorders.