In mammals, toll-like receptors (TLR) recognize ligands, including pathogen-associated molecular patterns (PAMPs), and respond with ligand-specific induction of genes. In this study, we establish evolutionary conservation in teleost fish of key components of the TLR-signaling pathway that act as switches for differential gene induction, including MYD88, TIRAP, TRIF, TRAF6, IRF3, and IRF7. We further explore this conservation with a molecular phylogenetic analysis of MYD88. To the extent that current genomic analysis can establish, each vertebrate has one ortholog to each of these genes. For molecular tree construction and phylogeny inference, we demonstrate a methodology for including genes with only partial primary sequences without disrupting the topology provided by the high-confidence full-length sequences. Conservation of the TLR-signaling molecules suggests that the basic program of gene regulation by the TLR-signaling pathway is conserved across vertebrates. To test this hypothesis, leukocytes from a model fish, rainbow trout (Oncorhynchus mykiss), were stimulated with known mammalian TLR agonists including: diacylated and triacylated forms of lipoprotein, flagellin, two forms of LPS, synthetic double-stranded RNA, and two imidazoquinoline compounds (loxoribine and R848). Trout leukocytes responded in vitro to a number of these agonists with distinct patterns of cytokine expression that correspond to mammalian responses. Our results support the key prediction from our phylogenetic analyses that strong selective pressure of pathogenic microbes has preserved both TLR recognition and signaling functions during vertebrate evolution.