In this paper, we propose an asymmetric adaptive modulation scheme for a heterogeneous two-way relay network (TWRN). In this scheme, due to the heterogeneity of the TWRN, different modulation schemes with different bit rates are assigned to the source nodes. Due to the mismatch between the bit rates of the two opposite traffic flows, the conventional XOR-based network coding is not applicable to this scheme. To cope with this heterogeneity at the relay node, we propose a network coding scheme in which the two data streams are combined at the level of symbol. We optimize the pair of modulation schemes and bit rates such that the instantaneous transmission rate is maximized under the constraint that a quality-of-service requirement in terms of the end-to-end BER is satisfied. To find the solution of this multi-dimensional problem, we propose a simple procedure with very low computational complexity by reducing the problem dimension to one. We analyze the system performance in terms of the average end-to-end BER, the average transmission rate, and the outage probability over Nakagami fading channel. Our analysis shows that this scheme not only achieves high spectral efficiency but also mitigates error propagation from the relay to the transceivers.