This paper investigates the feasibility of using cross-linked polyethylene (XLPE) waste as a partial replacement of conventional stone aggregates to produce concrete. Specifically, the effects of XLPE waste content (0, 5, 10, and 15 vol% of coarse and fine aggregates) and water-to-cement (W/C) ratio (0.45, 0.50, and 0.55) on the fresh properties (slump, unit weight, and air content) and hardened properties (bulk unit weight, ultrasonic pulse velocity, uniaxial compressive strength (UCS), split tensile strength (T), and flexural strength (F)) of concrete were investigated. Moreover, scanning electron microscopy (SEM) analysis was performed to study the interfacial transition zones (ITZs) at the different conditions. The results show that the addition of more XLPE improves the workability or slump (by 8% to 51%), decreases the unit weight (by 0.16% to 2.20%), but does not noticeably affect the air content of the fresh concrete (all ∼1.5%). Increasing the XLPE content results in a decrease of the UCS (by 23% to 60%) but improves the ductility and increases the T/UCS (by 19% to 144%) and F/UCS (by 22% to 174%) ratios of the concrete. The decrease of the UCS with a higher XLPE content is mainly due to the weaker ITZ between the XLPE and the binder. The study clearly indicates that the XLPE waste can partially replace the conventional stone aggregates to produce concrete for different applications specified by industry.