An apparatus and a method for transmitting a Coexistence Beacon Protocol (CBP) packet in a Cognitive Radio (CR) wireless communication system are provided. In the method for transmitting CBP packet in a transmitter that operates in a scalable Orthogonal Frequency Division Multiple Access (OFDMA) mode, a priority is given to each channel of one or more channels based at least partly upon channel use statuses of two or more neighbor Wireless Regional Area Networks (WRANs). Whether a Quality of Service (QoS) for CBP packet transmission for each channel is met is sequentially determined according to the respective priority. A channel having a highest priority is selected from the one or more channels meeting the QoS as a channel for CBP packet transmission. A CBP packet is transmitted via the selected channel.