Nontyphoidal salmonellae (NTS) are a leading cause of invasive disease in young children in sub-Saharan Africa. We used suppression subtractive hybridization (SSH) to identify 41 sequences within the accessory genome of an invasive strain of Salmonella Heidelberg from Malawi. PCR assays and database searches, used to determine the distribution of 14 SSH sequences among a panel of African and UK NTS isolates and published genomes, indicated that two were specific for S. Heidelberg. However, we found no evidence for major differences in the accessory genome content between African invasive and gastrointestinal isolates of S. Heidelberg. Six of the SSH sequences were within fimbrial operons. The tcf operon, associated with the host specificity of Salmonella Typhi, and the stk operon, reported previously in Salmonella Paratyphi, were both present in either all (tcf) or most (stk) isolates of S. Heidelberg, but had restricted distributions among the other serovars tested. Reverse transcription PCR analysis of seven SSH sequences indicated variable expression of the stk operon among isolates of S. Heidelberg. Three of the seven targeted genes were not expressed in a UK veterinary isolate of S. Heidelberg, suggesting that although genome content per se may not explain the different pathogenicity of the invasive isolates, it is possible that variations in gene expression may play a role.