A low complexity decoding technique with an essentially-ML performance for the Golden code and the 3 antenna Perfect code was introduced by Sirianunpiboon, Howard & Calderbank. Though no theoretical analysis of the decoder was given, the simulations showed that this decoding technique has almost maximum-likelihood (ML) performance. Inspired by this technique, in this paper we introduce two new low complexity decoders for Space-Time Block Codes (STBCs) - the Adaptive Conditional Zero-Forcing (ACZF) decoder and the ACZF decoder with successive interference cancellation (ACZF-SIC), which include as a special case the decoding technique of Sirianunpiboon et al. We show that both ACZF and ACZF-SIC decoders are capable of achieving full-diversity under Rayleigh fading, and we give sufficient conditions for an STBC to give full-diversity with these decoders. We then show that the Golden code, the 3 and 4 antenna Perfect codes, the 3 antenna Threaded Algebraic Space-Time code and the 4 antenna rate 2 code of Srinath & Rajan are all full-diversity ACZF/ACZF-SIC decodable with complexity strictly less than that of their ML decoders. Simulations show that the proposed decoding method performs identical to ML decoding for all these five codes. These STBCs along with the proposed decoding algorithm outperform all known codes in terms of both decoding complexity and error performance for Nt ≤ 4 transmit antennas. We further provide a lower bound on the complexity of full-diversity ACZF/ACZF-SIC decoding. The proposed decoders for all the five codes listed above achieve this lower bound and hence are optimal in terms of minimizing the ACZF/ACZF-SIC decoding complexity. © 2012 IEICE Institute of Electronics Informati.