Biological networks are inherently modular, yet little is known about how modules are assembled to enable coordinated and complex functions. We used RNAi and time series, whole-genome microarray analyses to systematically perturb and characterize components of a Caenorhabditis elegans lineage-specific transcriptional regulatory network. These data are supported by selected reporter gene analyses and comprehensive yeast one-hybrid and promoter sequence analyses. Based on these results, we define and characterize two modules composed of muscle- and epidermal-specifying transcription factors that function together within a single cell lineage to robustly specify multiple cell types. The expression of these two modules, although positively regulated by a common factor, is reliably segregated among daughter cells. Our analyses indicate that these modules repress each other, and we propose that this cross-inhibition coupled with their relative time of induction function to enhance the initial asymmetry in their expression patterns, thus leading to the observed invariant gene expression patterns and cell lineage. The coupling of asynchronous and topologically distinct modules may be a general principle of module assembly that functions to potentiate genetic switches.