Space-time block coded spatial permutation modulation (STBC-SPM) is a new MIMO technique that integraes the STBC-spatial modulation (STBC-SM) and the recently-proposed spatial permutation modulation (SPM). Specifically, SPM exploits the permutation vector to achieve diversity gain by dispersing the signal along the time coordinate. In this work, we examine the STBC-SPM in more details and propose a low-complexity decoder for STBC-SPM by utilizing the orthogonality of the STBC Alamouti code. The numerical simulations demonstrate the superior performance of the STBC-SPM from various aspects. Moreover, the proposed decoder structure achieves up to 90.6% 99. 9 % complexity saving without sacrificing the error rate performance, compared with the optimal maximum likelihood (ML) decoder implemented by the exhaustive search.