In this paper, we give a new framework for constructing low ML decoding complexity space-time block codes (STBCs) using codes over the Klein group K. Almost all known low ML decoding complexity STBCs can be obtained via this approach. New full-diversity STBCs with low ML decoding complexity and cubic shaping property are constructed, via codes over K, for number of transmit antennas N=2m, m ≥ 1, and rates R > 1 complex symbols per channel use. When R = N , the new STBCs are information-lossless as well. The new class of STBCs have the least known ML decoding complexity among all the codes available in the literature for a large set of (N,R) pairs. © 2006 IEEE.