This paper investigates the strength characteristics and stress-strain behaviors of waste fishing net (WFN)-added lightweight soil. The lightweight soil, which consisted of dredged soil, crumb rubber, and cement, was reinforced with WFN in order to increase its shear strength. Glue treated WFN was also added to lightweight soil to improve the interlocking between the soil mixture and WFN. Three kinds of test specimens were prepared: unreinforced lightweight soil, reinforced lightweight soil without glue treatment, and reinforced lightweight soil with glue treatment. Several series of laboratory tests were carried out, including flow value tests, unconfined compression tests, and SEM analyses. From the experimental results, it was found that the peak strength of the reinforced lightweight soil with glue treatment was increased by the increased interlocking between the soil mixture and WFN, which was induced from the bonding effect. The stress-strain relation of the reinforced lightweight soil, irrespective of the glue treatment, showed a more ductile behavior than that of the unreinforced lightweight soil.