The emerging need for high data rate wireless services has raised considerable interest in space-time coding. In this work, we propose a systematic code construction method that jointly considers diversity advantage and coding advantage for an arbitrary number of transmit antennas and any memoryless constellation. Our approach is to directly assign channel symbols to transmit antennas at different states by exploiting the properties of the state transitions in the trellis. The code construction problem is reduced to a combinatorial optimization problem and a computationally efficient suboptimal solution is proposed. The flexibility of the method is demonstrated by designing space-time trellis codes for QPSK, 8PSK, 16PSK, asymmetric QPSK and 4ASK constellations. Space-time code construction for a large number of transmit antennas (6, 8, and 10) is also considered. The simulations show that our design procedure results in codes that outperform the ones constructed by previously existing methods. The achievable performance gain is governed by the distance structure of the chosen constellation.