In this paper, we propose a novel multiple-input multiple-output (MIMO) transmission scheme, called trellis coded spatial modulation (TC-SM) in which a trellis (convolutional) encoder and a spatial modulation (SM) mapper are jointly designed similar to the conventional trellis coded modulation (TCM). A soft decision Viterbi decoder, which is fed with the soft information supplied by the optimal SM decoder, is used at the receiver. The pairwise error probability (PEP) upper bound is derived for the TC-SM scheme in uncorrelated quasi-static Rayleigh fading channels. From the PEP upper bound, code design criteria are given and then used to obtain new 4-, 8- and 16-state TC-SM schemes using QPSK (quadrature phase-shift keying) and 8-PSK modulations for 2 and 3 bits/s/Hz spectral efficiencies. It is shown via computer simulations that the proposed TC-SM schemes achieve significantly better error performance than their counterparts at the same spectral efficiency, yet with reduced decoding complexity.