In bony fish, the gill filaments are essential for gas exchanges, but also are vulnerable to infection by water-borne microorganisms. Omnipresent across fish, gill-associated lymphoid tissues (GIALT) regulate interactions with local microbiota and halt infection by pathogens. A special GIALT structure has recently been found in Salmonids, the interbranchial lymphoid tissue (ILT). However, the structural variation of GIALT across bony fish remains largely unknown. Here, we show how this critical zone of interaction evolved across fishes. By labeling a conserved T-cell epitope on tissue sections, we find that several basal groups of teleosts possess typical ILT, while modern teleosts have lymphoepithelium of different shape and size at the base of primary gill filaments. Within Cypriniformes, neither body size variation between two related species, zebrafish and common carp, nor morphotype variation, did have a drastic effect on the structure of ILT. Thereby this study is the first to describe the presence of ILT in zebrafish. The ILT variability across fish orders seems to represent different evolutionary solutions to balancing trade-offs between multiple adaptations of jaws and pharyngeal region, and immune responses. Our data point to a wide structural variation in gill immunity between basal groups and modern teleosts.