A novel reinforced recycled expanded polystyrene (r-EPS) foam/natural fiber composite was successfully developed. EPS was recycled by means of the dissolution method using an accessible commercial mixed organic solvent, while natural fibers, i.e., coconut husk fiber (coir) and banana stem fiber (BSF) were used as reinforcement materials. The treatment of natural fibers with 5% (w/v) sodium hydroxide solution reduces the number of –OH groups and non-cellulose components in the fibers, more so with longer treatments. The natural fibers treated for 6 h showed rough surfaces that provided good adhesion and interlocking with the polymer matrix for mechanical reinforcement. The tensile strength and impact strength of r-EPS foam composites with treated fibers were higher than for non-filled r-EPS foam, whereas their flexural strengths were lower. Thus, this study has demonstrated an alternative way to produce recycled polymer/natural fiber composites via the dissolution method, with promising enhanced mechanical properties.