Phylogenetic studies of the genus Plasmodium have been performed using sequences of the nuclear, mitochondrial and plastid genes. Here we have analyzed the adenylosuccinate lyase (ASL) gene, which encodes an enzyme involved in the salvage of host purines needed by malaria parasites for DNA synthesis. The ASL gene is present in several eukaryotic as well as prokaryotic organisms and does not have repeat regions, which facilitates the accuracy of the alignment. Furthermore, it has been shown that ASL is not subject to positive natural selection. We have sequenced the ASL gene of several different Plasmodium species infecting humans, rodents, monkeys and birds and used the obtained sequences along with the previously known P. falciparum ASL sequence, for structural and phylogenetic analysis of the genus Plasmodium. The genetic divergence of ASL is comparable with that observed in other nuclear genes such as cysteine proteinase, although ASL cannot be considered conserved when compared to aldolase or superoxide dismutase, which exhibit a slower rate of evolution. Nevertheless, a protein like ASL has a rate of evolution that provides enough information for elucidating evolutionary relationships. We modeled 3D structures of the ASL protein based on sequences used in the phylogenetic analysis and obtained a consistent structure for four different species despite the divergence observed. Such models would facilitate alignment in further studies with a greater number of plasmodial species or other Apicomplexa.