This paper deals with the problem of spectrum sharing among primary and secondary users in a cognitive radio. To use the spectrum efficiently and flexibly, the cognitive radio spectrum allocation problem was formulated as a graph coloring problem (GCP). However, GCP is known to be a nondeterministic polynomial-time (NP)-hard and cannot be solved for the practical system. Inspired by the efficiency of the cross-entropy (CE) method for finding near-optimal solutions in huge search spaces, this paper proposes the application of the CE method to allocate cognitive radio spectrum to achieve near-optimal spectrum utilization. Simulation results show that the average reward values obtained using the proposed CE method are better than those obtained using the conventional method.