A novel distributed power control (DPC) scheme for cellular networks in the presence of radio channel uncertainties such as path loss shadowing, and Rayleigh fading is presented. Since these uncertainties can attenuate the received signal strength and can cause variations in the received Signal-to-lnterference ratio (SIR), the proposed DPC scheme maintains a target SIR at the receiver provided the uncertainty is slowly varying with time. The DPC estimates the time varying nature of the channel quickly and uses the information to arrive at a suitable transmitter power value . Further, the standard assumption of a constant interference during a link's power update used in other work in the literature is relaxed. A CDMA-hased celluar network environment is used to compare the proposed scheme with earlier approaches. The results show that our DPC scheme can converge faster than others by adapting to the channel variations. The proposed DPC scheme can render outage prohability of 5 to 30% in the presence of uncertainties compared with other schemes of 50 to 90% while consuming law power per active mobile user. In other words, the proposed DPC scheme allows significant increase in network capacity while consuming low- power values even when the channel is uncertain.