Spatial modulation (SM), which employs the indices of multiple transmit antennas to transmit information in addition to the conventional M-ary signal constellations, is a novel transmission technique that has been proposed for multiple-input multiple-output systems. In this study, a new class of space-time trellis codes, called ‘super-orthogonal trellis-coded SM’ (SOTC-SM), is proposed. These codes combine set partitioning and a super set of space-time block coded SM (STBC-SM) codewords to achieve maximal diversity and coding gains by exploiting both SM and space-time block codes. Unlike super-orthogonal space-time trellis codes (SOSTTCs), which parametrise the orthogonal STBCs, these new codes expand the antenna constellation using the principle of SM. Systematic construction methods are presented for the SOTC-SM scheme and design examples are given for 2, 4 and 8 trellis states, at 2, 3 and 4 bits/s/Hz spectral efficiencies. The approximate bit-error probability performance of SOTC-SM is derived and shown to match computer simulation results. A simplified maximum likelihood detection method for the proposed scheme is given. It is shown through computer simulations that the proposed SOTC-SM schemes achieve significantly better error performance than SOSTTCs with comparable complexity.