Small RNAs (sRNAs) are a class of gene regulators in bacteria, playing a central role in their response to environmental changes. Bioinformatic prediction facilitates the identification of sRNAs expressed under different conditions. We propose a novel method of prediction of sRNAs from the genome of Agrobacterium based on a positional weight matrix of conditional sigma factors. sRNAs predicted from the genome are integrated with the virulence-specific transcriptome data to identify putative sRNAs that are overexpressed during Agrobacterial virulence induction. A total of 384 sRNAs are predicted from transcriptome data analysis of Agrobacterium fabrum and 100-500 sRNAs from the genome of different Agrobacterial strains. In order to refine our study, a final set of 10 novel sRNAs with best features across different replicons targeting virulence genes were experimentally identified using semi-quantitative polymerase chain reaction. Since Ti plasmid plays a major role in virulence, out of 10 sRNAs across the replicons, 4 novel sRNAs differentially expressed under virulence induced and non-induced conditions are predicted to be present in the Ti plasmid T-DNA region flanking virulence-related genes like agrocinopine synthase, indole 3-lactate synthase, mannopine synthase and tryptophan monooxygenase. Further validation of the function of these sRNAs in conferring virulence would be relevant to explore their role in Agrobacterium-mediated plant transformation.