In this paper, we propose to reduce the complexity of both the Approx-Log-MAP algorithm as well as of the Max-Log-MAP algorithm, which were designed for soft-decision-aided Space-Time Block Code (STBC) detectors. First of all, we review the STBC design, which enables regular L-PSK/QAM detectors to be invoked in order to detect STBCs on a symbol-by-symbol basis. Secondly, we propose to operate the L-PSK/QAM aided STBC detection on a bit-by-bit basis, so that the complexity may be reduced from the order of O(L) to O(BPS = log 2 L). Our simulation results demonstrate that a near-capacity performance may be achieved by the proposed detectors at a substantially reduced detection complexity. For example, a factor six complexity reduction was achieved by the proposed algorithms, when they were invoked for detecting Alamouti's Square 16QAM aided G2 scheme.