In this paper, we propose a novel application of Redundant Residue Number System (RRNS) codes to Space-Time Block Codes (STBCs) design. Based on the so-called “Direct-Mapping” scheme, the link between residues and complex signal constellations is optimized. We derive upper bounds on the codeword error probability of RRNS-STBC and characterize its achievable diversity gain assuming maximum likelihood decoding (MLD). The knowledge of apriori probabilities of residue generation is utilized to implement a probability based Distance-Aware Direct Mapping scheme for M-ary modulation which further improves the error performance of the RRNS-STBC coding scheme.