The genome of Paramecium undergoes a remarkable reorganization during the development of the macronucleus. Tens of thousands of mostly short sequences are interspersed in the micronuclear genome, often interrupting protein reading frames. During the macronuclear development, these internal eliminated sequences (IESs) are precisely excised and thus the macronuclear genes are fully functional. The role, if any, of IESs, their evolutionary history and dynamics as well as the molecular mechanism(s) involved in their excision are still far from resolved. As a first step towards exploring these questions we here performed a large scale systematic reconstruction of the evolutionary history of IESs in Paramecium. We focused on 7 species from the aurelia species complex and used P. caudatum as an outgroup. We sequenced the micronuclear and, when not available, the macronuclear genomes of each species and annotated genes and IESs. We specifically focused on conserved genes that can be aligned across species in order to find homologous IESs. We inferred the phylogenies of each gene family and reconciled the resulting gene trees with the species tree. Using a Bayesian approach we inferred the ancestral states of presence and absence for each IES. The result is an unprecedented detailed description of the evolutionary history of tens of thousands of IESs. Preliminary results validate previous models of IES evolution. We find that there was a wave of insertion of IESs after the split of the aurelia species complex from P. caudatum and subsequently the rate of gain and loss of IESs was significantly reduced. Our detailed description of IES evolutionary history also enables us to compare the age of acquisition of different IESs with various genomic properties. For example we find that recently inserted IESs are on average longer. We believe that our results will fuel further studies to test models and gain new insights on the molecular mechanisms of genomic rearrangements in the developing macronucleus.