The formation of an incapacitating biofilm on Caenorhabditis elegans by Yersinia pseudotuberculosis represents a tractable model for investigating the genetic basis for host-pathogen interplay during the biofilm-mediated infection of a living surface. Previously we established a role for quorum sensing (QS) and the master motility regulator, FlhDC, in biofilm formation by Y. pseudotuberculosis on C. elegans. To obtain further genome-wide insights, we used transcriptomic analysis to obtain comparative information on C. elegans in the presence and absence of biofilm and on wild-type Y. pseudotuberculosis and Y. pseudotuberculosis QS mutants. Infection of C. elegans with the wild-type Y. pseudotuberculosis resulted in the differential regulation of numerous genes, including a distinct subset of nematode C-lectin (clec) and fatty acid desaturase (fat) genes. Evaluation of the corresponding C. elegans clec-49 and fat-3 deletion mutants showed delayed biofilm formation and abolished biofilm formation, respectively. Transcriptomic analysis of Y. pseudotuberculosis revealed that genes located in both of the histidine utilization (hut) operons were upregulated in both QS and flhDC mutants. In addition, mutation of the regulatory gene hutC resulted in the loss of biofilm, increased expression of flhDC, and enhanced swimming motility. These data are consistent with the existence of a regulatory cascade in which the Hut pathway links QS and flhDC. This work also indicates that biofilm formation by Y. pseudotuberculosis on C. elegans is an interactive process during which the initial attachment/recognition of Yersinia to/by C. elegans is followed by bacterial growth and biofilm formation.