In this letter, we investigate employing Trellis Coded Modulation (TCM) in an Orthogonal Frequency Division Multiple Access (OFDMA) based secondary system in an underlay cognitive radio network. While it is expectable for channel coding to improve the performance in the secondary service compared to the uncoded case at the expense of rate reduction, our results indicate that the benefits of such utilization is beyond expectation. In fact we show that for a given bandwidth and bit error rate performance, the coded scheme not only requires less average transmit power per subcarrier, but it also provides a significantly higher sum-rate compared to the uncoded case. This result is against the well-known property of channel coding in conventional communication systems where we sacrifice effective date rate to reduce the required power for a given bit error rate. This is due to the fact that using TCM in the secondary system, we successfully transmit bits with a lower transmit power. Having a transmission with lower transmit power, we would be able to transmit with a higher bit rate in the secondary system and still meet the interference threshold requirements in the primary network. Total rate is increased if the increase due to lower transmit power beats the decrease caused by coding. Our simulation results show that this is indeed the case for TCM-OFDMA secondary system.