A wireless device stores historical information for a prior access attempt and uses this information to lower the output transmit power for a current access attempt on an access channel. The historical information may include RF conditions for the prior access attempt, the performance for the prior access attempt, and a power value used for the prior access attempt. The power value may be a power adjustment or an initial power level. For the current access attempt, the wireless device obtains the historical information, determines the current RF conditions, and determines a power value for this access attempt based on the current RF conditions and the historical information. The wireless device determines the output power for each access probe based on the power value and other applicable parameters and sends each access probe at the determined output power. The wireless device updates the historical information upon completing the access attempt.