This paper addresses the effects of nonlinearity of flows on the value of the productivity index (PI) of the well. Experimental data show that, during the dynamic process of hydrocarbon recovery, the PI stabilizes to some constant value, which, in general, is a nonlinear function of both the pressure drawdown and the production rate. Linear Darcy flow is well understood, and excellent approximate formulas are available for the PI in various well/reservoir geometries. To handle the more realistic nonlinear situation, the current practice is to solve the nonlinear problem multiple times for different values of production rate and then add ad-hoc corrective parameters in the linear formulas to reproduce the nonlinear nature of the flow. In this paper, we propose a rigorous framework to measure the PI of a well for nonlinear Forchheimer flows. Our approach, based on recent progress in the modeling of transient Forchheimer flows, uses both analytical and numerical techniques. It provides, for a wide class of reservoir geometries, an accurate relation between the PI for nonlinear Forchheimer flows and the PI for linear Darcy flows. The proposed method of building look-up tables and analytical formulas serves as an effective tool for fast PI evaluation in nonlinear cases.