Surface-active asphaltene molecules are naturally found in crude oil, causing serious problems in the petroleum industry by stabilizing emulsion drops, thus hindering the separation of water and oil. Asphaltenes can adsorb at water-oil interfaces to form viscoelastic interfacial films that retard or prevent coalescence. Here, we measure the evolving interfacial shear rheology of water-oil interfaces as asphaltenes adsorb. Generally, interfaces stiffen with time, and the response crosses over from viscous-dominated to elastic-dominated. However, significant variations in the stiffness evolution are observed in putatively identical experiments. Direct visualization of the interfacial strain field reveals significant heterogeneities within each evolving film, which appear to be an inherent feature of the asphaltene interfaces. Our results reveal the adsorption process and aged interfacial structure to be more complex than that previously described. The complexities likely impact the coalescence of asphaltene-stabilized droplets, and suggest new challenges in destabilizing crude oil emulsions.