A new framework is proposed to study the co-clustering of gene expression data. This framework is based on a generic tensor optimization model and an optimization method termed Maximum Block Improvement (MBI) recently developed in . Not only can this framework be applied for co-clustering gene expression data with genes expressed at different conditions represented in 2D matrices, but it can also be readily applied for co-clustering more complex high-dimensional gene expression data with genes expressed at different tissues, different development stages, different time points, different stimulations, etc. Moreover, the new framework is so flexible that it poses no difficulty at all to incorporate a variety of clustering quality measurements. In this paper, we demonstrate the effectiveness of this new approach by providing the details of one specific implementation of the algorithm, and presenting the experimental testing on microarray gene expression datasets. Our results show that the new algorithm is very efficient and it performs well for identifying patterns in gene expression datasets.