A base station includes an apparatus and a method for exchanging frequency channel resources between base stations in a Cognitive Radio (CR) based communication system. A requesting Base Station (BS), which requests channel exchange a neighboring BS, receives a channel advertisement message from a neighboring BS and sends a channel exchange request message to the neighboring BS. The channel exchange request message includes at least one of a neighbor BS Identifier (ID), a requesting BS ID, channel information for the channel exchange at the requesting BS, and channel information exchangeable at the neighboring BS. The requesting BS receives a channel exchange response message from the neighboring BS in response to the channel exchange request message, determines whether to execute a channel exchange process to the neighboring BS based on information in the received channel exchange response message, and sends a channel exchange reply message indicative of the determination result.