Influence of filler network on Payne effect and modulus recovery for vapor grown carbon nanofiber (VGCF)/polystyrene (PS) composites with VGCF content above electrical percolation threshold was studied by using simultaneous measurements of viscoelasticity and electrical conductivity. The strain softening seems to be closely related to breakdown of filler network. Recovery tests of modulus and electrical conductivity by means of time sweep indicate that the reformation of deformed VGCF network structure could not be completed in several hours. Compared with recovery behavior of carbon black (CB) and silica (SiO2) network, the reformation of VGCF network appears more difficult. Moreover, solidification of composites exerts some effect on modulus recovery. The filler network disrupted by small strain can be perfectly recovered by matrix solidification while the initial filler structure collapsing at large strain is only partially restored.