This work presents a novel modeling technique to investigate the role of certain microstructural properties on the mechanical performance of asphalt mixtures. The methodology initiates by randomly creating probable microstructures of asphalt mixtures. Then, these random microstructures are implemented in a Finite Element (FE) software to evaluate their mechanical response using a viscoelastic–viscodamage constitutive relationship. The role of aggregate gradation and air void content on the mechanical deterioration of asphalt mixtures was studied. The results suggest that these properties significantly impact damage initiation and propagation within asphalt materials, as well as the uncertainty associated with these degradation processes.