In this paper we present an efficient scheme employing a multi-user data predistortion algorithm for compensation of the nonlinear channel in the forward link of a wireless multiple access MC-CDMA system. The signal constellations of all the active users are jointly and iteratively optimized by taking into account the multiple access interference degrading the performance at the relevant decision devices. A simplified method is described which makes the iterative procedure simple to implement and enables to trade off performance and complexity. It is shown through simulation that higher performance are achieved with respect to a conventional memoryless predistortion technique.