Despite being a major group of intracellular pathogens, the role of class I-restricted T cells in the clearance of Gram-negative bacteria is not resolved. Using a murine typhoid model, a role for class I-restricted T cells in the immune response to the Gram-negative pathogen Salmonella typhimurium is revealed. Class I-deficient β 2-microglobulin−/− mice show increased susceptibility to infection with S. typhimurium. Following infection, CD8+ CTLs specific for Salmonella-infected targets can be readily detected. The Salmonella-specific CTLs recognize infected H-2-mismatched targets, suggesting the involvement of shared class Ib molecules. Studies using transfectants expressing defined class Ia and class Ib molecules indicate the involvement of the class Ib molecule, Qa-1. Ab-blocking studies and the measurement of bacteria-specific CTL frequencies identified Qa-1 as a dominant restricting element. The Qa-1-restricted CTL recognition depends on TAP and proteasome functions. Surprisingly, Qa-1-restricted CTLs recognized cells infected with other closely related Gram-negative bacteria. Taken together, these observations indicate that Salmonella-specific CTLs recognize a cross-reactive epitope presented by Qa-1 molecules and, as such, may be novel targets for vaccine development.