Agrobacterium tumefaciens is a plant pathogen that has the natural ability of delivering and integrating a piece of its own DNA into plant genome. Although bacterial non-coding RNAs (ncRNAs) have been shown to regulate various biological processes including virulence, we have limited knowledge of how Agrobacterium ncRNAs regulate this unique inter-Kingdom gene transfer. Using whole transcriptome sequencing and an ncRNA search algorithm developed for this work, we identified 475 highly expressed candidate ncRNAs from A. tumefaciens C58, including 101 trans-encoded small RNAs (sRNAs), 354 antisense RNAs (asRNAs), 20 5′ untranslated region (UTR) leaders including a RNA thermosensor and 6 riboswitches. Moreover, transcription start site (TSS) mapping analysis revealed that about 51% of the mapped mRNAs have 5′ UTRs longer than 60 nt, suggesting that numerous cis-acting regulatory elements might be encoded in the A. tumefaciens genome. Eighteen asRNAs were found on the complementary strands of virA, virB, virC, virD, and virE operons. Fifteen ncRNAs were induced and 7 were suppressed by the Agrobacterium virulence (vir) gene inducer acetosyringone (AS), a phenolic compound secreted by the plants. Interestingly, fourteen of the AS-induced ncRNAs have putative vir box sequences in the upstream regions. We experimentally validated expression of 36 ncRNAs using Northern blot and Rapid Amplification of cDNA Ends analyses. We show functional relevance of two 5′ UTR elements: a RNA thermonsensor (C1_109596F) that may regulate translation of the major cold shock protein cspA, and a thi-box riboswitch (C1_2541934R) that may transcriptionally regulate a thiamine biosynthesis operon, thiCOGG. Further studies on ncRNAs functions in this bacterium may provide insights and strategies that can be used to better manage pathogenic bacteria for plants and to improve Agrobacterum-mediated plant transformation.