The rise of the World Airline Network over the past century has led to sharp changes in our notions of “distance” and “closeness”—in terms of both trade and travel, but also (less desirably) with respect to the spread of disease. When novel pathogens are discovered, countries, cities, and hospitals are caught trying to predict how much time they have to prepare. In this paper, by considering the early stages of epidemic spread as a simple branching process, we derive the full probability distribution of arrival times. We are able to rederive a number of past arrival time results (in suitable limits) and demonstrate the robustness of our approach, both to parameter values far outside the traditionally considered regime and to errors in the parameter values used. The branching process approach provides some theoretical justification to the “effective distance” introduced by Brockmann and Helbing [Science 342, 1337 (2013)]; however, we also observe that when compared to real-world data, the predictive power of all methods in this class is significantly lower than has been previously reported.