Electrochromic technologies that exhibit low power consumption have been spotlighted recently. In particular, with the recent increase in demand for paper-like panel displays, faster coloration time has been focused on in researching electrochromic devices. Tungsten trioxide (WO3) has been widely used as an electrochromic material that exhibits excellent electrochromic performance with high thermal and mechanical stability. However, in a solid film-type WO3 layer, the coloration time was long due to its limited surface area and long diffusion paths of lithium ions (Li-ions). In this study, we attempted to fabricate a fibrous structure of WO3@poly(ethylene oxide) (PEO) composites through electrospinning. The fibrous and porous layer showed a faster coloration time due to a short Li-ion diffusion path. Additionally, PEO in fibers supports Li-ions being quickly transported into the WO3 particles through their high ionic conductivity. The optimized WO3@PEO fibrous structure showed 61.3 cm2/C of high coloration efficiency, 1.6s fast coloration time, and good cycle stability. Lastly, the electrochromic device was successfully fabricated on fabric using gel electrolytes and a conductive knitted fabric as a substrate and showed a comparable color change through a voltage change from −2.5 V to 1.5 V.