We propose a simple data analysis procedure that aims to uncover an association between gene expression and the status of a clinical outcome variable. Rather than focus on differences in group means, as is usually done, we search for pairs of genes such that the strength or direction of their association is linked to the value of the outcome variable. This more complex pattern of gene expression, which we call “differential correlation”, may be especially relevant in studying clinical outcomes such as survival and grade, since it has often been difficult to identify marker genes whose mean expression varies directly with such outcomes. In applying our method to two lung cancer microarray data sets, we discovered that a substantially greater number of genes are likely to be associated with clinical outcomes such as tumor stage via differential correlation than are associated via changes in mean expression.