Model-based phylogenetic studies of homologous sequences of nucleotides often assume that the underlying evolutionary process was stationary, reversible, and homogeneous (SRH) over the tree. However, an increasing body of data suggests that evolution under these conditions is an exception, rather than the norm. Moreover, there is growing evidence of convergent evolution, not only at the phenotypic level but also at the genotypic level. In 2014, we introduced a family of mixture models (HAL-HAS) that approximate heterogeneity in the substitution process across lineages and across sites. Subsequently, this model was found to return biased results when convergence had occurred during the evolution. Here we present a new algorithm (HAL-HAS 2) that overcomes these issues. Based on simulation-based analyses of alignments of nucleotides generated on a 4-tipped tree with convergent evolution, the accuracy of phylogenetic estimates improved from 26% to 98%. Results obtained using data sets with 20 or 30 sequences showed that the algorithm is also accurate when a larger number of models are considered. When applying HAL-HAS 2 to a real data set obtained from eight yeast genomes, a model of evolution that includes convergence and rate heterogeneity across lineages as well as sites provides a better fit to these data than other models of evolution do.