Road rehabilitation and reconstruction generate large supplies of reclaimed asphalt pavement (RAP) aggregate, and recycling into asphalt paving mixtures is the predominant application. Cement kiln dust (CKD), also known as cement bypass dust, is a by-product material generated during production of portland cement. In Oman, where recycling of pavement materials is not practiced, a first attempt was made at combining two by-product materials for use in road construction. Conservation of natural resources and preservation of the environment are two benefits that could be gained by reusing waste materials. The potential use in road bases of CKD-stabilized RAP and RAP with virgin aggregate mixtures was investigated. Physical, compaction, and unconfined compressive strength tests were conducted on RAP and virgin aggregate blends of 100% to 0%, 90% to 10%, 80% to 20%, and 0% to 100%. Samples were prepared using CKD at 0%, 3%, 5%, 7%, 10%, 15%, and 20% and were cured for 3, 7, and 28 days in plastic bags at room temperature. Results indicate that the maximum dry density and unconfined compressive strength of RAP generally increase with addition of virgin aggregate and CKD. The moisture content-dry density curves for CKD-stabilized RAP aggregate mixtures did not show a distinctive peak similar to that of the 100% virgin aggregate blend. Longer curing periods will produce higher strength values. CKD content of 15% seems to be the optimum for achieving maximum strength.