Gene network, conventionally, is learned by studying the pairwise correlation of the microarray expression profiles of different genes. This approach, however, is reported to be effective only for learning a small portion of the regulatory pairs due to the complexity of the gene regulatory system. In this paper, through studying the conditional dependence of the gene expression profiles, a new algorithm, Conditional Dependence Learning algorithm, is proposed which considers three additional factors: (1) the collaboration among regulators, (2) the formation of regulatory complex, and (3) the variable time delay to learn the gene network. Experiments on both artificial and real-life gene expression datasets validate the goodness of the algorithm.