Emerging evidence suggest that the heterogeneity of cancer limits the efficacy of immunotherapy. To search for optimal therapeutic targets for enhancing the efficacy, we used whole-exome sequencing data of 23 early cervical tumors from Chinese women to investigate the hierarchical structure of the somatic mutations and the neo-epitopes. The putative neo-epitopes were predicted based on the mutant peptides' strong binding with major histocompatibility complex class I molecules. We found that each tumor carried an average of 117 mutations and 61 putative neo-epitopes. Each patient displayed a unique phylogenetic tree in which almost all subclones harbored neo-epitopes, highlighting the importance of individual neo-epitope tree in determination of immunotherapeutic targets. The alterations in FBXW7 and PIK3CA, or other members of the significantly altered ubiquitin-mediated proteolysis and extracellular matrix receptor interaction related pathways, were proposed as the earliest changes triggering the malignant progression. The neo-epitopes involved in these pathways, and located at the top of the hierarchy tree, might become the optimal candidates for therapeutic targets, possessing the potential to mediate T-cell killing of the descendant cells. These findings expanded our understanding in early stage of cervical carcinogenesis and offered an important approach to assist optimizing the immunotherapeutic target selection.