A new type of time-dependent and strain-history-dependent viscoelasticity was discovered in semidilute polymer solutions. Dynamic moduli G′ and G″ of 20% and 10% nitrile butadiene rubber (NBR) solutions were recorded as a function of time while oscillatory shear deformations were maintained. The moduli decrease with time was observed only at lower frequencies. The time dependence ofG′was more pronounced than that ofG″. At a higher temperature, the time dependence was extended toward higher frequencies also, and the time dependence became stronger. Lowering the concentration of solution gave a similar effect as increasing temperature. After the cessation of oscillations, a slow recovery was observed. The recovery was somewhat faster at the higher temperature. The time-dependent moduli and their recovery were explained by the change and recovery of structures associated with long branches and gels in the NBR. The structure change occurred at higher frequencies also, but it was not observed during the application of oscillation. Only in subsequent measurements at lower frequencies could the structure change be detected. Thus, the change may be regarded as strain history dependent. The mechanism of the structural change was explained with either the entanglement or osmotic pressure models, depending on concentration.