Problems associated with waste generation from different industrial productions have escalated with technological advancements worldwide. Fiber molding wastes (FMW) are a prime example required proper management. Recycling wastes is an effective solution for reducing environmental impacts, conserving natural resources and enhancing sustainable development. Hence, the utilization of waste materials in construction is crucial for sustainable development. This study explores the suitability of FMW as natural fine aggregate (NFA) for casting paving blocks sized 200 mm × 100 mm × 60 mm. Initially, materials were tested following British Standards (BS). Three percentages of crushed FMW: 10%, 15%, and 25%, were utilized to substitute NFA in M15 grade concrete mixture prepared using the British Department of the Environment (DOE) mix design method to cast paving blocks. Simultaneously, control samples of paving blocks were produced and cured in water for various durations to evaluate the optimal product. Subsequently, block samples were tested for compressive strength at 7 and 28 days and water absorption properties. Additionally, how the water-cement (W/C) ratio was influenced on the compressive strength of three FMW mixed paving blocks can be identified. The outcomes showed that with increment of the W/C ratio value, compressive strength of paving blocks was decreased, and the highest compressive strength was achieved by concrete mixture with 0.791 W/C ratio. Furthermore, it was observed that increasing the replacement of FMW led to higher water absorption results. Ultimate compressive strength test results demonstrated that gradual decrease in compressive strength with the increase of substituting crushed FMW as NFA. However, the study concluded that as per SLS 1425 - Part 1:2011, paving blocks containing up to 25% FMW that exhibited compressive strength exceeding 15 MPa after 28 days satisfied pedestrian requirements excluding vehicle accesses.