Techniques are provided for performing early decoding of a message on a control channel in a wireless (e.g., GSM) communication system. In a GSM system, a message for a paging channel is transmitted in four bursts. For early decoding in GSM, a terminal initially receives the first two bursts for the message. The two bursts are processed and decoded to recover the message, which is then checked to determine whether it has been decoded correctly or in error. The decoding process can terminate and the terminal may go to sleep early if the recovered message is good. Otherwise, the third burst is received, and all three bursts are processed and decoded to recover the message. Again, the decoding process can terminate if the recovered message is good. Otherwise, the fourth burst is received, and all four bursts are processed and decoded to recover the message.