In recent years adaptive modulation has emerged as a popular technique to improve data throughput and system capacity in a wireless system. The basic idea is to adapt the modulation scheme to the fading channel quality, using different schemes for different channel conditions. Therefore one primary issue is to determine the switching thresholds between the modulation schemes. Typically these thresholds are fixed according to a certain criterion. This paper introduces a novel adaptive learning approach that is capable of dynamically adjusting the thresholds so as to maximize the throughput. A key feature of the proposed self-learning scheme is that no dedicated training signal is required, instead it utilizes the long-term average throughput to continuously update the thresholds as the data is transmitted.