Utilization of low-quality aggregates in the eastern province of Saudi Arabia as well as in most Gulf areas is becoming a necessity. In this area, the definition of low-quality aggregates is more related to surface chemistry characteristics and salt content than to particle strength, porosity, surface texture, organic and fines or any other deficiency measures. Stripping, ravelling, and rutting are the major distress manifestations observed in asphaltic mixtures. Rutting is related to mix flow. Bleeding and shoving problems are also observed but to a lesser extent. One effective solution to the above is the cement coating of the coarse aggregate, thereby eliminating surface chemistry debonding behavior (stripping) and increasing the overall mixture stiffness. Several laboratory testing methods on aggregates (such as specific gravity, water absorption, abrasion, and soundness) and on asphaltic mixtures (such as stability, modulus of resilience, creep and rutting, fracture toughness, and index of retained strength) have been performed. Laboratory test results on cement-coated and uncoated aggregates as well as on their asphaltic mixtures clearly indicate the improvements obtained by cement coating technique. These improvements include more than 30% increase in Marshall stability with flow remaining within specification range, improved coating and resistance to stripping, increased tensile strength and resilient modulus, more than 90% immersion-tensile strength ratio, and increased fatigue life.