This paper introduces a new S-T coding scheme, namely Space-Time Complementary Coding (STCC) scheme. With the help of pair-wise complementary codes, the proposed STCC scheme can achieve transmitter diversity and parallel transmission at the same time. It will be shown that the STCC scheme can easily be generalized to achieve arbitrary combination of diversity gain and parallel transmission order. The new scheme requires neither bandwidth expansion nor feedback information from the receiver, and it offers a nearly interference-free performance. The analytical study will be carried out in this paper to show that it provides a very high diversity-multiplexing product gain for its operation in both flat and frequency-selective fading channels.