The use of Roller Compacted Concrete Pavement (RCCP) is widely expanding throughout the world because of its benefits of reduced cement content, early opening to traffic, economic benefits and high speed of implementation over the conventional concrete pavements. The lower cement content of RCC requires careful selection of an aggregate structure to ensure the adequate structural performance of the pavement. Recommended gradation bands have been proposed by different works of literature with few studies systematically investigating aggregate gradation effects on the properties of RCC. In this study, a laboratory investigation was conducted to quantify the effects of varying cement and fines content of aggregates on the compressive and tensile strength of RCC mixes. In the experimental work, 24 type of mixtures of RCCP with varying cement contents (285, 297.4 and 319.7kg/m³) and eight different fines contents (0.41 – 15.5% by total aggregate weight) were made use of. Two category of fines content were used among which four of them had 0.41 – 1.42% fines content while the rest four had 7.5 – 15.5% fines content values. The test results showed that the compressive strength of lower fines content mixes increases as the percentage of fines content increases. Even though the minimum required compressive strength at a cement content of 285kg/m³ was 20 MPa, the results from the experiment revealed that a maximum of 23.88 MPa and a minimum of 22.42 MPa compressive strength values were obtained at fines content of 1.42% and 0.41% of the total aggregate weight; respectively. The compressive strength of all of the lower fines content mixes, at 28 days of concrete age, increases as the fines content of the mix increases. For higher fines content mixes, the compressive strength for the mixes with a fines content of not more than 10.5% gives the required compressive strength value. Whereby, the results of tests on low fines content mixes indicated that the increase in fines content above 0.62% by weight of the total aggregate up to the recommended value gives a considerable decrease in tensile strength of RCC mixes. Besides, there was a considerable loss in tensile strength as the amount of fines in the mix increases above 7.5% by the weight of the total aggregate.