Without measures of the lethality of terrorist networks, it is very difficult to assess if capturing or killing a terrorist is effective. We present the predictive lethality analysis of terrorist organization () algorithm, which merges machine learning with techniques from graph theory and social network analysis to predict the number of attacks that a terrorist network will carry out based on a network structure alone. We show that is highly accurate on two novel datasets, which cover Al Qaeda (AQ) and the Islamic State (ISIS). Using both machine learning and statistical methods, we show that the most significant macrofeatures for predicting AQ’s lethality are related to their public communications (PCs) and logistical subnetworks, while the leadership and operational subnetworks are most impactful for predicting ISISs lethality. Across both groups, the average degree and the diameters of the strongly connected components (SCCs) within these networks are strongly linked with lethality.