Channel fading can have a strong impact on the convergence of over-the-air federated edge learning (OTA-FEEL). This paper develops a new and optimal power control policy to minimize the optimality gap of OTA-FEEL under any independently and identically distributed fading. Specifically, we reveal that the optimal power control policy takes a structure where the variance of the effective channel from a device to the server should be minimized when its mean is given. Following this structure, a novel nested optimization algorithm is developed to iteratively minimize the variance using the Lagrange-dual method and then optimize the mean of the effective channel using one-dimensional search. A quasi-closed-form expression of the optimal power control policy is derived. It is shown that the optimal adaptive power control for OTA-FEEL performs an integration of the “channel inverting” strategy and the opposite “channel-proportional” strategy to balance the mean and variance of the effective channel. We also generalize the new policy when the channel statistics are unknown a-priori, and show that the optimal policy can be asymptotically approached over time. Simulations confirm the superiority of the policy to its existing alternatives in the convergence speed and learning accuracy of OTA-FEEL.