A polynomial predistortion apparatus and method for compensating for a nonlinear distortion characteristic of a power amplifier is provided. The apparatus and method comprise an adaptation controller for determining polynomial coefficients by calculating an inverse nonlinear distortion characteristic of the power amplifier, and calculating complex predistortion gains for all possible amplitudes of an input signal using the determined polynomial coefficients; and a predistorter for receiving an input signal which is a combination of complex-modulated previous baseband input signal samples and current input signal samples, predistorting the input signal using the complex predistortion gains output from the adaptation controller, and outputting the predistorted input signal to the power amplifier.