The computational, mathematical, and statistical study of evolutionary trees relies on enumerative studies of discrete combinatorial structures in phylogenetics. Enumerations characterize spaces of trees and networks, assist in probabilistic computations under evolutionary models, and guide analyses of computational complexity for phylogenetic algorithms. This talk will examine the topic of combinatorial enumeration in mathematical phylogenetics, with an emphasis on new results concerning a fundamental structure: the labeled histories that arise in probability models of evolutionary trees.