We derive the outage capacity regions of an M-user fading multiple-access channel under the assumption that both the transmitters and the receiver have perfect channel side information. We show that the outage capacity region is implicitly obtained by deriving the outage probability region for a given rate vector. Given the average power constraint and the required rate of each user, we find a successive decoding strategy and a power allocation policy that bound the outage probability region. Also discussed is a simpler minimum common outage probability problem under the assumption that the multiple-access channel is either not used at all when fading is severe or is used simultaneously by all users. Iterative algorithms are proposed for obtaining the optimal decoding order and power allocation in each fading state under the given power constraint of each user.