Background: The evolution of complex organs is thought to occur via a stepwise process, each subsequent step increasing the organ’s complexity by a tiny amount. Studying this process requires closely related species that vary in the complexity of their organs. This is the case for the placenta in the livebearing fish family Poeciliidae, as members of this family vary markedly in their placental complexity. Here, we look for the genomic basis underlying this phenotypic variation in the genome of Heterandria formosa, a poeciliid fish with a highly complex placenta. We compare this genome to three published reference genomes of non-placental poeciliid fish to gain insight in which genes play a role in the evolution of the placenta in the Poeciliidae. Results: We sequenced the genome of H. formosa, providing the first whole genome sequence information of a placental poeciliid. We looked for signatures of adaptive evolution by comparing its gene sequences to those of three non-placental live-bearing relatives. We found 18 positively selected genes exclusive to H. formosa, as well as 5 gene duplications. Eight of the genes evolving under positive selection in H. formosa have a placental function in mammals, most notably endometrial tissue remodelling or endometrial cell proliferation. Conclusions: Our results show that a substantial portion of positively selected genes have a function that correlates well with the morphological changes that form the placenta of H. formosa, compared to the corresponding tissue in non-placental poeciliids. These functions are mainly endometrial tissue remodelling and endometrial cell proliferation. Therefore, we hypothesize that natural selection acting on genes involved in these functions plays a key role in the evolution of the placenta in H. formosa.