Animal cells in tissues are supported by biopolymer matrices, which typically exhibit highly nonlinear mechanical properties. While the linear elasticity of the matrix can significantly impact cell mechanics and functionality, it remains largely unknown how cells, in turn, affect the nonlinear mechanics of their surrounding matrix. Here, we show that living contractile cells are able to generate a massive stiffness gradient in three distinct 3D extracellular matrix model systems: collagen, fibrin, and Matrigel. We decipher this remarkable behavior by introducing nonlinear stress inference microscopy (NSIM), a technique to infer stress fields in a 3D matrix from nonlinear microrheology measurements with optical tweezers. Using NSIM and simulations, we reveal large long-ranged cell-generated stresses capable of buckling filaments in the matrix. These stresses give rise to the large spatial extent of the observed cell-induced matrix stiffness gradient, which can provide a mechanism for mechanical communication between cells.