A pavement’s structure gradually deteriorates due to repeated traffic load and environmental effects. These effects lead to distresses such as permanent deformation, fatigue cracking and thermal cracking. Granular base course stabilization using asphalt emulsion is one the most popular techniques to enhance the layer performance in order to achieve sufficient bearing capacity and resistance to pavement distresses. The major drawbacks of asphalt emulsion-stabilized base course, though, are its low early strength, long curing time, and low resistance to permanent deformation and moisture damage. To address these drawbacks, the asphalt emulsion-stabilized layer is usually modified with cement, which can improve its early strength and performance properties. However, using the cement makes the treated base course more prone to shrinkage cracking. Asphaltenes is a waste material derived from Alberta oil-sands with no significant use in the pavement industry. Asphaltenes is one of the polar fractions of asphalt binder, and its addition to asphalt binder has been found to have a considerable effect in increasing stiffness. In this context, the present study compares the impact of cement versus asphaltenes on the asphalt emulsion-stabilized base performance properties. For this purpose, different concentrations of cement and asphaltenes (1% and 2% per weight of total mixture) are added to asphalt mixtures, and the mechanical properties of the mixtures, including the low-temperature performance, are evaluated. It is concluded that both asphaltenes and cement are effective in improving a mixture’s strength and rutting resistance. However, cement-modified mixtures are found to be more prone to low-temperature cracking than are asphaltenes-modified mixtures.