The influence of different types of polyethylene (PE) substitutions as partial aggregate replacement of microsteel fiber-reinforced self-consolidating concrete (SCC) incorporating incinerator fly ash was investigated. The study focuses on the workability and hardened properties including mechanical properties, permeability properties, sulfate resistance, and microstructure. Regardless of the polyethylene type, PE substitutions slightly decreased the compressive and flexural strength of SSC initially; however, the difference was compensated at later ages. Scanning electron microscope (SEM) analysis of the interfacial transition zone showed that there was chemical interaction between PE and the matrix. Although PE substitutions increased the permeable porosity and sorptivity, it significantly improved the sulfate resistance of SCC. The influence of PE shape and size on workability and strength was found to be more important than its type. When considering the disposal of PE wastes and saving embodied energy, consuming recycled PE as partial aggregate replacement was more advantageous over virgin PE aggregate-replaced concrete.