An apparatus and a method for saving power of a mobile station (MS). The apparatus includes an RF unit for processing radio signals transmitted between an MS and a BS, and a processor for performing an RX task, a layer 2 task, a main control task, and a searcher task. The RX task receives a message from the BS by controlling the RF unit, determining if an address included in the received message matches an address stored in the MS, transmitting the received message to another task when the address match, and generating a fast sleep command when the address do not match. The layer 2 task transmits the message received from the RX task to another task, the main control task processes the message, and the searcher task shifts the MS to a fast sleep state when receiving the command from the RX task.