This paper investigates the critical impacts of the void morphology on the strength and damage responses of asphalt concrete as a time-dependent heterogeneous medium. First, efficient algorithms are developed to randomly fabricate the void morphology within a realistic microstructural representation of asphalt concrete. The algorithms take voids’ fundamental characteristics such as the content, shape, and size distribution into account to generate random void morphologies. Then, a nonlinear viscoelastic-viscodamage formulation based on principles of damage mechanics is used to run finite element simulations of the fabricated microstructures. The effects of varying the characteristics of voids are assessed in terms of stress distribution and damage evolution. Finally, a probabilistic analysis is conducted to evaluate the impacts of random void morphologies on the mechanical responses of asphalt concrete microstructural representations. The results indicate that unrealistic void representations lead to an overestimate in the strength of this time-dependent heterogeneous medium, and emphasize the importance of considering realistic void morphologies in mechanical analyses. The outcome shows that the developed algorithms provide a viable numerical tool to produce realistic representations of asphalt concrete.