This study experimentally evaluates the influence of quarry dust as a partial replacement for natural river sand in the performance of interlocking paving blocks. Five replacement levels; 0%, 2.5%, 5%, 7.5% and 10% by mass of sand, were investigated using a nominal 1:2:4 mix proportion and a constant water–cement ratio of 0.70. Sixty interlocking specimens were produced, with three specimens from each mixture tested at 7, 14, 21 and 28 days. Preliminary characterization included particle-size distribution and specific gravity of the aggregates, while the fresh concrete was assessed using the slump test. The hardened specimens were evaluated through density and compressive-strength measurements. The specific gravities of the natural sand and quarry dust were 2.45 and 2.57, respectively. Slump reduced from 20 mm for the control mixture to 10.5 mm at 2.5% replacement and 0 mm at 5–10% replacement, indicating a marked increase in water demand as quarry dust content increased. Despite the reduction in workability, the compressive-strength results showed that the 2.5% mixture performed poorly, whereas strength increased progressively from 5% to 10% replacement. At 28 days, the control mixture recorded 7.47 N/mm², compared with 4.93, 5.90, 6.70 and 6.82 N/mm² for 2.5%, 5%, 7.5% and 10% replacement, respectively. The 10% mixture therefore gave the highest strength and density among the quarry-dust mixtures tested, although it did not exceed the control strength. The results indicate that quarry dust can be beneficial as a limited sand-replacement material in paving-block production when adequate compaction and mix-water control are provided. The study recommends 10% as the optimum replacement within the investigated range, while emphasizing that this conclusion is specific to the materials and mix conditions used.