Many techniques have been developed to solve biclustering gene expression datasets problem by minimizing the crossings in the input matrices like cHawk  and Bimax . The usage of local searching techniques - in the step of Crossing Minimization (CM) - causes some limitations that affect the accuracy of the obtained biclusters. In this paper, Crossing Minimization Biclustering Algorithm (CMBA) is proposed that deals with this issue. CMBA algorithm consists of two main steps: Crossing Minimization and biclusters Identification. In the former step, two global search techniques: Tabu Search (TS) and Greedy Randomized Adaptive Search Procedure (GRASP) are investigated. While identification step, the Mean Squared Residue (MSR) is used as a measurement for the similarity in the input data. The results show that the CMBA algorithm is competitive to other heuristic techniques. Also, CMBA is able to improve the accuracy for both the low density matrices and the high density matrices. Also, using the MSR approach makes CMBA competitive to well-known C&C algorithm .