This paper proposes a Slotted Aloha with Decollision Algorithm (SADA) medium access control (MAC) protocol for satellite uplink access. The basic Slotted Aloha MAC protocol has a maximum throughput of about 0.37 at an offered load of one packet per slot. In the Satellite Automatic Identification System (AIS), decollision algorithms are used to decode signals of packets transmitted in the same access slot. The key idea of the proposed SADA MAC protocol is to make use of a decollision algorithm to enhance throughput. This paper shows the performance analysis of the proposed SADA MAC protocol which can achieve tremendous throughput gain of more than 10 times (10×) with a decollision algorithm that is capable of decoding up to 8 packets in a slot of a frame.