This letter introduces two fast maximum-likelihood (ML) detection methods for 4*4 quasi-orthogonal space-time block code (QOSTBC). The first algorithm with a relatively simple design exploits structure of quadrature amplitude modulation (QAM) constellations to achieve its goal and the second algorithm, though somewhat more complex, can be applied to any arbitrary constellation. Both decoders utilize a novel decomposition technique for ML metric which divides the metric into independent positive parts and a positive interference part. Search spaces of symbols are substantially reduced by employing the independent parts and statistics of noise. Finally, the members of search spaces are successively evaluated until the metric is minimized. Simulation results confirm that the proposed decoder is superior to some of the most recently published methods in terms of complexity level. More specifically, the results verified that application of the new algorithm with 1024-QAM would require reduced computational complexity compared to state-of-the-art solution with 16-QAM.