In this paper, we introduce the concept of multi-dimensional (MD) space-time shift keying (STSK) for improving conventional STSK schemes, while still maintaining the general STSK structure for backward compatibility. Firstly, we design two transmission modes for three-dimensional (3-D) STSK schemes, referred to as R2 3-D STSK and R3 3-D STSK, with the incorporation of 3-D constellations. In addition, we devise a joint optimization mechanism utilizing the modified simplified conjugate gradient (SCG) algorithm to enhance the achievable system performance of R3 3-D STSK, through a harmonized design of the constellation and the dispersion matrix set. Furthermore, we derive the optimal combinations of the 3-D constellation coordinates for R2 3-D STSK by maximizing the minimal determinant of the difference matrices. Then, we extend 3-D STSK to the MD STSK family, offering a flexible and efficient performance enhancement mechanism for STSK systems. Extensive simulation results are provided to show the tradeoffs among link performance, diversity order and signal dimensionality of the proposed MD STSK scheme, illustrating a good way to upgrade conventional STSK systems.