It is estimated that to overcome rolling resistance (RR) a typical vehicle, on average, consumes 4152 MJ/119 L of fuel annually, depending not only on vehicle-related factors but also on pavement-related factors. A slight improvement in surface properties may thus decrease fuel consumption, bringing substantial long-term socioeconomic benefits per capita per country. This aligns with ever-tighter limits on CO2 in the European Union (95 g/km until 2021), fostering sustainable construction and exploitation of tires and pavements. This paper outlines a newly developed multiscale three-dimensional numerical methodology to quantify texture-dependent RR due to indentation of aggregates into viscoelastic tread compound. It consists of a microscale tread block single-aggregate model and a macroscale car tire finite element model, rolling in a steady-state mode over a rigid smooth surface. Microscale interaction rates are deduced from the macroscale model. Tread compound is simulated by application of a time-dependent, linear, viscoelastic model. The microscale simulations enabled quantification of RR induced by an arrangement of surface aggregates. The outlined texture-dependent RR estimates are based on contact force moment around the contact patch center. The computed contact force results show a significant peak of normal force due to viscoelastic and inertia effects at the onset of the tire–surface contact phase, followed by a gradually decreasing/relaxing stress region with a sudden release at the end of the interaction. The contact forces seem to be of a reasonable distribution and magnitude. The proposed approach allows prediction of RR losses due to compressive forces at the microscale. Macro-distortional RR (which is not the subject of this paper) would then have to be added to find the total tire-related RR.