Small non-coding RNAs with important regulatory roles are not confined to eukaryotes. Recent work has uncovered a growing number of bacterial small RNAs (sRNAs), some of which have been shown to regulate critical cellular processes. Computational approaches, in combination with molecular experiments, have played an important role in the identification of these sRNAs. At present, there is no information on the presence of small non-coding RNAs and their genes in the Agrobacterium tumefaciens genome. To identify potential sRNAs in this important bacterium, deep sequencing of the short RNA populations isolated from Agrobacterium tumefaciens C58 was carried out. From a data set of more than 10,000 short sequences, 16 candidate sRNAs have been tentatively identified based on computational analysis. All of these candidates can form stem-loop structures by RNA folding predictions and the majority of the secondary structures are rich in GC base pairs. Some are followed by a short stretch of U residues, indicative of a rho-independent transcription terminator, whereas some of the short RNAs are found in the stem region of the hairpin, indicative of eukaryotic-like sRNAs. Experimental strategies will need to be used to verify these candidates. The study of an expanded list of candidate sRNAs in Agrobacterium will allow a more complete understanding of the range of roles played by regulatory RNAs in prokaryotes.