Multiuser diversity refers to a type of diversity present across different users in a fading environment. This diversity can be exploited by scheduling transmissions so that users transmit when their channel conditions are favorable. Using such an approach leads to a system capacity that increases with the number of users. However, such scheduling requires centralized control. In this paper, we consider a decentralized medium access control (MAC) protocol, where each user only has knowledge of its own channel gain. We consider a variation of the ALOHA protocol, channel-aware ALOHA; using this protocol we show that users can still exploit multi-user diversity gains. First we consider a backlogged model, where each user always has packets to send. In this case we show that the total system throughput increases at the same rate as in a system with a centralized scheduler. Asymptotically, the fraction of throughput lost due to the random access protocol is shown to be 1/e. We also consider a splitting algorithm, where the splitting sequence depends on the users’ channel gains; this algorithm is shown to approach the throughput of an optimal centralized scheme. Next we consider a system with an infinite user population and random arrivals. In this case, it is proved that a variation of channel-aware ALOHA is stable for any total arrival rate in a memoryless channel, given that users can estimate the backlog. Extensions for channels with memory are also discussed.