The phenomenon of icing, and the derived processes for its mitigation, are of great importance in many applications, ranging from transportation and energy to food and refrigeration. This phenomenon has been studied mostly with respect to its manifestation on rigid, homogeneous surfaces, with soft materials being the topic of more recent investigations. Although, icing often occurs on substrates that are chemically and mechanically heterogeneous, e.g., widely used asphalt concrete, which consists of rigid aggregates embedded in soft bitumen, to date, ice adhesion behavior on such substrates needs to be better understood. Here, we study ice adhesion stresses - the stresses necessary to remove ice - of ice blocks on heterogeneous materials, juxtaposing the behavior of the two main constituents of asphalt concrete, the rigid aggregates (modeled by Macor®) and bitumen, to the behavior of bitumen-Macor® composites. We show that the ice adhesion shear stress on Macor® is almost twice as large as that on bitumen, whereas the ice adhesion normal stress and the normal and shear components of composite stress are in a similar range. We synthesize composite substrates that consist of bitumen stripes on Macor® and find that increasing bitumen width leads to lower ice adhesion stress, while the stripe direction with respect to the applied force direction has a minor effect. Based on our findings, we then coat the most ice-adhesive component (Macor®) with a thin superhydrophobic coating and show that this can reduce ice adhesion stress on the heterogeneous substrates. We also find that for ice formed half on bitumen and half on Macor®, if Macor® is first and bitumen second with respect to the applied force direction (material order), then the measured ice adhesion stress is less compared to the reverse case in material order.