A novel multiple-input multiple-output (MIMO) transmission scheme, called space-time block coded spatial modulation (STBC-SM), is proposed. It combines spatial modulation (SM) and space-time block coding (STBC) to take advantage of the benefits of both while avoiding their drawbacks. In the STBC-SM scheme, the transmitted information symbols are expanded not only to the space and time domains but also to the spatial (antenna) domain which corresponds to the on/off status of the transmit antennas available at the space domain, and therefore both core STBC and antenna indices carry information. A general technique is presented for the design of the STBC-SM scheme for any number of transmit antennas. Besides the high spectral efficiency advantage provided by the antenna domain, the proposed scheme is also optimized by deriving its diversity and coding gains to exploit the diversity advantage of STBC. A low-complexity maximum likelihood (ML) decoder is given for the new scheme which profits from the orthogonality of the core STBC. The performance advantages of the STBC-SM over simple SM and over V-BLAST are shown by simulation results for various spectral efficiencies and are supported by the derivation of a closed form expression for the union bound on the bit error probability.