We measure the dynamical mechanical properties of human red blood cells. A single cell response is measured with optical tweezers. We investigate both the stress relaxation following a fast deformation and the effect of varying the strain rate. We find a power-law decay of the stress as a function of time, down to a plateau stress, and a power-law increase of the cell's elasticity as a function of the strain rate. Interestingly, the exponents of these quantities violate the linear superposition principle, indicating a nonlinear response. We propose that this is due to the breaking of a fraction of the crosslinks during the deformation process. The soft glassy rheology model accounts for the relation between the exponents we observe experimentally. This picture is consistent with recent models of bond remodeling in the red blood cell's molecular structure. Our results imply that the blood cell's mechanical behavior depends critically on the deformation process.