We present a fast and robust atlas-based algorithm for labeling airway trees, using geodesic distances in a geometric tree-space. Possible branch label configurations for an unlabeled airway tree are evaluated using distances to a training set of labeled airway trees. In tree-space, airway tree topology and geometry change continuously, giving a natural automatic handling of anatomical differences and noise. A hierarchical approach makes the algorithm efficient, assigning labels from the trachea and downwards. Only the airway centerline tree is used, which is relatively unaffected by pathology. The algorithm is evaluated on 80 segmented airway trees from 40 subjects at two time points, labeled by three medical experts each, testing accuracy, reproducibility and robustness in patients with chronic obstructive pulmonary disease (COPD). The accuracy of the algorithm is statistically similar to that of the experts and not significantly correlated with COPD severity. The reproducibility of the algorithm is significantly better than that of the experts, and negatively correlated with COPD severity. Evaluation of the algorithm on a longitudinal set of 8724 trees from a lung cancer screening trial shows that the algorithm can be used in large scale studies with high reproducibility, and that the negative correlation of reproducibility with COPD severity can be explained by missing branches, for instance due to segmentation problems in COPD patients. We conclude that the algorithm is robust to COPD severity given equally complete airway trees, and comparable in performance to that of experts in pulmonary medicine, emphasizing the suitability of the labeling algorithm for clinical use.