This paper reports on using waste polyethylene to form plastic-bonded sand interlocking blocks for wall construction. The production process, mechanical properties, and failure mechanisms of three different interlocking block wall systems are reported. Plastic-bonded composite blocks were formed by mixing sand into waste polyethylene in a high-temperature extruder. The blocks formed had densities between 1.5 and 1.6 g cm⁻³ and compressive strengths of approximately 15.0 MPa. This is significantly higher than the conventional sandcrete wall blocks that are widely used in developing countries. The blocks were used to construct walls with dimensions of 1.0 m × 1.0 m × 0.15 m, and these were subjected to in-plane compressive loads. The compressive strengths of the walls ranged from 4.2 to 5.7 MPa. Variations in the block composition did not affect the failure mechanism, but the extent of the block damage after failure varied significantly. The potential for using waste plastics to form interlocking construction blocks for use in low-cost construction is discussed.