Spatial modulation (SM) is a promising multiple-input multiple-output system used to increase spectral efficiency. The maximum likelihood (ML) decoder jointly detects the transmitted SM symbol, which is of high complexity. In this paper, a novel reliable sphere decoder (RSD) algorithm based on tree-search is proposed for the SM system. The basic idea of the proposed RSD algorithm is to reduce the size of the tree-search, and then, a smart searching method inside the reduced tree-search is performed to find the solution. The proposed RSD algorithm provides a significant reduction in decoding complexity compared to the ML decoder and existent decoders as well. Moreover, the RSD algorithm provides a flexible trade-off between the bit error rate (BER) performance and decoding complexity, so as to be reliable for a wide range of practical hardware implementations. The BER performance and decoding complexity analysis for the RSD algorithm are studied, and Monte Carlo simulations are then provided to demonstrate the findings.