We show that the well-known Kohn anomaly predicts Tc for ordered AlB2-type structures. We use ab initio density functional theory to calculate phonon dispersions for Mg1-xAlxB2 compositions and identify a phonon anomaly with magnitude that predicts experimental values of Tc for all x. Key features of these anomalies correlate with the electronic structure of Mg1-xAlxB2. This approach predicts Tc for other known AlB2-type structures as well as new compositions. We predict that Mg0.5Ba0.5B2 will show Tc = 63.6 ± 6.6 K. Other forms of the Mg1-xBaxB2 series will also be superconductors when successfully synthesised. Our calculations predict that the end-member composition, BaB2, is likely to show a Tc significantly higher than currently achieved by other diborides although an applied pressure ∼16 GPa may be required to stabilise the structure.