The non-structural model of heat exchanger networks (HENs) offers a wide solution space for optimization due to the random matching of hot and cold streams. However, this stochastic matching can sometimes result in infeasible structures, leading to inefficient optimization. To address this issue, a tabu matching based on a heuristic algorithm for HENs is proposed. The proposed tabu-matching method involves three main steps: First, the critical temperature levels—high, medium, and low-temperature intervals—are determined based on the inlet and outlet temperatures of streams. Second, the number of nodes is set according to the temperature intervals. Third, the nodes of streams are flexibly matched within the tabu rules: the low-temperature interval of hot streams with the high-temperature interval of cold streams; the streams crossing cannot be matched. The results revealed that by incorporating the tabu rules and adjusting the number of nodes, the ratio of the feasible zone in the whole solution domain increases, and the calculation efficiency is enhanced. To evaluate the effectiveness of the method, three benchmark problems were studied. The obtained total annual costs (TACs) of these case studies exhibited a decrease of USD 4290/yr (case 1), USD 1435/yr (case 2), and USD 11,232/yr (case 3) compared to the best published results. The results demonstrate that the proposed tabu-matching heuristic algorithm is effective and robust.