OFDMA is a popular coding scheme for mobile wireless communications. In OFDMA, one must allocate the available resources (bandwidth and power) dynamically, as user requests arrive and depart in a stochastic manner. Several exact and heuristic methods exist to do this, but they all perform poorly in the “over-loaded” case, in which the user demand is close to or exceeds the system capacity. To address this case, we present a dynamic local search heuristic. A particular feature of our heuristic is that it takes fairness into consideration. Simulations on realistic data show that our heuristic is fast enough to be used in real-time, and consistently delivers allocations of good quality.