Cestodes of the order Trypanorhyncha can frequently be found infecting the muscles of several marine fish species, and lead to a repugnant aspect of the fish and rejection by consumers. The Brazilian sardinella, Sardinella brasiliensis, occurs from the Gulf of Mexico and the Caribbean to northern Uruguay. In southeastern Brazil, fishing for the species is very intensive since it generates significant revenue as one of the most commonly consumed fish and an important element of the canned fish industry. The aims of the present study were to identify and report the occurrence of tiny cestodes (3 mm-6.6 mm) in the musculature of Brazilian sardinella that were purchased in the São Pedro fish market in the municipality of Niterói, state of Rio de Janeiro, Brazil. From October 2013 to November 2016, 75 specimens of S. brasiliensis were investigated. The trypanorhynch cestodes encountered were identified as plerocerci of Callitetrarhynchus gracilis using morphological, morphometric and molecular data. Parasitic indices were calculated, and the cestodes infection of the musculature of Brazilian sardinella had the following values: prevalence, 40%; mean intensity, 3.47; mean abundance, 1.39; and range of infection, 1-18, specimens. The presence of this trypanorhynch cestode in the musculature of Brazilian sardinella is an important indicator of fish hygiene.