The Villari effect of magnetostrictive materials, a change in magnetization due to an applied stress, is used for sensor/energy harvesting applications. In this work, magnetostrictive fiber/polymer composites are fabricated for the first time by embedding strong textured Fe–Co fibers in an epoxy matrix, and their stress-rate dependent output voltage characteristics are investigated. Compression tests are first conducted to measure the output voltage of a sample. A simple magnetomechanical coupling model of the magnetostrictive fiber/polymer composite is then established. The output voltage is predicted, and domain wall dynamics is discussed in relation to the macroscopic inverse magnetostrictive response (known as the Villari effect). The results show that the output voltage density of this novel Fe–Co fiber/polymer composite dramatically increases with increasing stress-rate and becomes larger than that of Fe-Ga alloy. Our work represents an important step forward in the development of magnetostrictive sensor and energy harvesting materials.