In this paper, a layered tabu search (LTS) algorithm for a complex-valued channel matrix (LTS-C) is developed to provide optimal detection in large MIMO systems. The proposed LTS-C algorithm works directly on the complex-valued channel matrix rather than converting it to a real-valued matrix. The contribution of this paper is twofold. First, we propose a novel neighborhood approach based on a signal constellation graph to obtain a set of neighborhoods for the given complex-valued initial vector. Second, the tabu matrix structure is changed to track complex-valued moves. The proposed structure significantly reduces the size of the tabu matrix. Our simulation results show that the complexity reduction is substantial in the LTS-C algorithm over the LTS algorithm. In particular, LTS-C is able to achieve approximately 45–50% and 93–94% of complexity reduction in terms of the number of real operations for 16×16 and 32×32 MIMO systems, respectively. © 2017 Elsevier GmbH