The advent of new sequencing technologies has provided access to genome-wide markers which may be evaluated for their association with phenotypes. Recent studies have leveraged these technologies and sequenced hundreds and sometimes thousands of strains to improve the accuracy of genotype-phenotype predictions. Sequencing of thousands of strains is not practical for many research groups which argues for the formulation of new strategies to improve predictability using lower sample sizes and more cost-effective methods. We introduce here a novel computational algorithm called POPSICLE that leverages the local genetic variations to infer blocks of shared ancestries to construct complex evolutionary relationships. These evolutionary relationships are subsequently visualized using chromosome painting, as admixtures and as clades to acquire general as well as specific ancestral relationships within a population. In addition, POPSICLE evaluates the ancestral blocks for their association with phenotypes thereby bridging two powerful methodologies from population genetics and genome-wide association studies. In comparison to existing tools, POPSICLE offers substantial improvements in terms of accuracy, speed and automation. We evaluated POPSICLEs ability to find genetic determinants of Artemisinin resistance within P. falciparum using 57 randomly selected strains, out of 1,612 that were used in the original study. POPSICLE found Kelch, a gene implicated in the original study, to be significant (p-value 0) towards resistance to Artemisinin. We further extended this analysis to find shared ancestries among closely related P. falciparum, P. reichenowi and P. gaboni species from the Laverania subgenus of Plasmodium. POPSICLE was able to accurately infer the population structure of the Laverania subgenus and detected 4 strains from a chimpanzee in Koulamoutou with significant shared ancestries with P. falciparum and P. gaboni. We simulated 4 datasets to asses if these shared ancestries indicated a hybrid or mixed infections involving P. falciparum and P. gaboni. The analysis based on the simulated data and genome-wide heterozygosity profiles of the strains indicate these are most likely mixed infections although the possibility of hybrids cannot be ruled out. POPSICLE is a java-based utility that requires no installation and can be downloaded freely from https://popsicle-admixture.sourceforge.io/\n\nAuthor SummaryThe associations between genotypes and phenotypes have traditionally been performed using markers such as single nucleotide polymorphisms. Often, these markers are independently evaluated for their association with phenotypes. A genomic region is deemed significant if multiple markers with significance colocalize. However, multiple markers that are in linkage disequilibrium can sometimes work synergistically and contribute to phenotypic variations. These synergistic associations across markers and across subpopulations have traditionally been captured by population genetic approaches that determine local ancestries. We sought to bridge these two powerful but independent methodologies to improve genotype-phenotype predictions. We developed a new software called POPSICLE that employs an innovative approach to determine local ancestries and evaluates them for their association with phenotypes. Validity of POPSICLE in determining the genes that are responsible for Plasmodium Falciparums resistance to Artemisinin and in determining the population structure of Laverania subgenus of Plasmodium are discussed.