Relaxation dynamics of entangled polymer liquids are investigated in nonlinear step shear flow using mechanical rheometry experiments and theory. Entangled solutions of high molar mass polystyrenes (PS), 3 x 10(5) less than or equal to phiM(w) x 10(6) g/mol, in diethyl phthalate (DEP) are the main focus of this study. Cone-and-plate rheometer fixtures roughened by attachment of a single layer of 10-30 pro silica glass beads are used to eliminate interfacial slip during step shear measurements. A simple theory for stress relaxation dynamics that accounts for coupled relaxation of molecular orientation, chain stretching, and entanglement density is used to analyze the experimental results. In PS/DEP solutions with phiM(w) greater than or equal to 5 x 105 and in which PS forms an average of eight or more entanglements per chain, we find that the nonlinear relaxation modulus can be factorized into separate strain-dependent and time-dependent functions only after a time lambda(k2) approximate to tau(d0) similar to (phiM(w))(3) substantially larger than the longest Rouse relaxation time tau(Rouse) of the solution. This finding is consistent with results from a previous study of step shear dynamics in solutions of ultrahigh molecular weight polystyrene, M-w = 2.06 x 10(7) [Sanchez-Reyes, J.; Archer, L. A. Macromolecules 2002, 35, 51941, but contradicts expectations from current theories for entangled polymer dynamics, which predict lambda(k2) approximate to (3 - 5)tau(Rouse). The origin of this discrepancy is traced to a greater than expected influence of entanglement loss and recovery processes on polymer relaxation dynamics in nonlinear step shear flow.