Newly emerging influenza A viruses (IAV) pose a major threat to human health by causing seasonal epidemics and/or pandemics, the latter often facilitated by the lack of pre-existing immunity in the general population. Early recognition of candidate pandemic influenza viruses (CPIV) is of crucial importance for restricting virus transmission and developing appropriate therapeutic and prophylactic strategies including effective vaccines. Often, the pandemic potential of newly emerging IAV is only fully recognized once the virus starts to spread efficiently causing serious disease in humans. Here, we used a novel phylogenetic algorithm based on the informational spectrum method (ISM) to identify potential CPIV by predicting mutations in the viral hemagglutinin (HA) gene that are likely to (differentially) affect critical interactions between the HA protein and target cells from bird and human origin, respectively. Predictions were subsequently validated by generating pseudotyped retrovirus particles and genetically engineered IAV containing these mutations and characterizing potential effects on virus entry and replication in cells expressing human and avian IAV receptors, respectively. Our data suggest that the ISM-based algorithm is suitable to identify CPIV among IAV strains that are circulating in animal hosts and thus may be a new tool for assessing pandemic risks associated with specific strains.