We present a unified construction of full-diversity space-time block codes (STBC) called orthogonality-embedded space-time (OEST) codes. Other existing STBC, including orthogonal, quasi-orthogonal and rate-one linear threaded algebraic space-time (LTAST) codes, can also be derived from OEST codes. The new OEST construction is of the form Sigma(A(k) circle times C-k + B-k circle times C-k(H)), where A(k) and B-k are linear-dispersion matrices of orthogonal STBC and C(k)s are circulant matrices. The circulant matrices encode the data vectors, which can be completely separately detected at the receiver, greatly reducing the decoding complexity. For the same number of transmit antennas. several variants of OEST codes can be constructed allowing a tradeoff among the rate, performance and decoding complexity. A new rate-one STBC derived from OEST codes, called semi-orthogonal algebraic space-time codes, is shown to achieve near capacity of multi-input single-output channels and performs better than several existing STBC. Copyright (C) 2007 John Wiley & Sons, Ltd.