In this paper, we investigate a trellis-coded space shift keying modulation scheme, called trellis-coded space-time shift keying (TC-STSK), which combines trellis-coded modulation with space shift keying. By analyzing the rank criterion using a graph theoretic approach, we maximize the number of unique differences between pairwise codewords as the code design goal. We discuss the code design principles for achieving diversity, and propose a design algorithm that is mostly suitable for rate-1/n codes, where n is the number of the code output bits. We then propose a diversity adaptation mechanism by selecting only the codewords with desired diversity, and use it to design higher rate codes that achieve full diversity. We also provide the code designs and a modified soft Viterbi decoder for such schemes. Simulation results show that the proposed scheme can achieve diversity orders expected from the theoretical analysis, and that increasing the number of shift registers and transmit antennas improves the performance of the TC-STSK scheme. The results also show that TC-STSK outperforms a space-time trellis code with the same bit rate and the number of shift registers.