This study evaluates the use of Paper Mill Sludge (PMS) waste as a partial replacement for fine aggregate in paving block production, focusing on compressive strength and economic feasibility. PMS was incorporated at 0%, 5%, 10%, 15%, and 20% of the total fine aggregate weight. Compressive strength tests followed the Indonesian National Standard (SNI 03-0691-1996), accompanied by production cost analysis. The results showed that 5% PMS achieved the highest compressive strength of 264.23 kg/cm², about 7.7% higher than the control 258.71 kg/cm², meeting the SNI quality class B (K200) standard. Meanwhile, 10% PMS reduced production costs by 6–8% while still satisfying the minimum requirement for K200 paving blocks (category B). This demonstrates a clear trade-off between mechanical performance and cost efficiency, where 5% PMS ensures maximum strength, while 10% PMS provides adequate strength with economic benefits. At lower levels, PMS fibers improved cement–aggregate bonding and reduced voids, whereas higher dosages (>10%) disrupted hydration and lowered strength. Practically, PMS utilization offers the paving block industry a sustainable and cost-effective alternative that reduces reliance on natural aggregates, supports waste valorization, and aligns with SNI standards for applications such as parking lots.