Space-time block coded spatial modulation (STBC-SM), which employs space-time block coding (STBC) for spatial modulation (SM), is proposed as a new multiple-input multiple-output (MIMO) transmission scheme. 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, therefore both core STBC and antenna indices carry information. A general framework is presented for the design of the STBC-SM scheme for any number of transmit antennas. The proposed scheme is 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. It is shown by computer simulations that STBC-SM provides approximately 3-5 dB (depending on the spectral efficiency) better error performance than SM and V-BLAST systems.