To enhance the symbol error rate (SER) performance of the two-way relay channels with physical layer network coding, this letter proposes a relay selection scheme, in which the relay with the maximal minimum distance between different points in its constellation among all relays is selected to assist two-way transmissions. We give the closed-form expression of minimum distance for binary phase-shift keying and quadrature phase-shift keying. Additionally, we design a low-complexity method for higher-order modulations based on look-up tables. Simulation results show that the proposed scheme improves the SER performance for two-way relay networks.