A method of handling frequency de-prioritization for a communication device in a wireless communication system is disclosed. The method comprises receiving a first Radio resource control (RRC) connection reject message with a first deprioritization request indicating at least one first carrier frequency to be the lowest priority frequency, from a first public land mobile network (PLMN) of the wireless communication system, and determining the at least one first carrier frequency to be the lowest priority frequency only when the communication device selects or registers to the first PLMN.