General algebraic space-time code constructions are presented for Gray-mapped 2K-PSK, 2K-PAM, and 4K-QAM constellations. The space-time codes achieve the rate-diversity tradeoff—i.e., they allow the transmission of information at the maximum rate possible for the given signaling constellation and the achieved transmit diversity level. New codes created by applying a nonsingular linear or affine transformation to the constellation labels retain the optimality of the original codes with respect to the rate-diversity tradeoff. Extensions to pK-PSK, pK-PAM, p2K-QAM, and related constellations, for p prime, are also given.