The species from the order Xanthomonadales, which harbors many important plant pathogens and some human pathogens, are currently distinguished primarily on the basis of their branching in the 16S rRNA tree. No molecular or biochemical characteristic is known that is specific for these bacteria. Phylogenetic and comparative analyses were conducted on 26 sequenced Xanthomonadales genomes to delineate their branching order and to identify molecular signatures consisting of conserved signature indels (CSIs) in protein sequences that are specific for these bacteria. In a phylogenetic tree based upon sequences for 28 proteins, Xanthomonadales species formed a strongly supported clade with Rhodanobacter sp. 2APBS1 as its deepest branch. Comparative analyses of protein sequences have identified 13 CSIs in widely distributed proteins such as GlnRS, TypA, MscL, LysRS, LipA, Tgt, LpxA, TolQ, ParE, PolA and TyrB that are unique to all species/strains from this order, but not found in any other bacteria. Fifteen additional CSIs in proteins (viz. CoxD, DnaE, PolA, SucA, AsnB, RecA, PyrG, LigA, MutS and TrmD) are uniquely shared by different Xanthomonadales except Rhodanobacter and in a few cases by Pseudoxanthomonas species, providing further support for the deep branching of these two genera. Five other CSIs are commonly shared by Xanthomonadales and 1-3 species from the orders Chromatiales, Methylococcales and Cardiobacteriales suggesting that these deep branching orders of Gammaproteobacteria might be specifically related. Lastly, 7 CSIs in ValRS, CarB, PyrE, GlyS, RnhB, MinD and X001065 are commonly shared by Xanthomonadales and a limited number of Beta- or Gamma-proteobacteria. Our analysis indicates that these CSIs have likely originated independently and they are not due to lateral gene transfers. The Xanthomonadales-specific CSIs reported here provide novel molecular markers for the identification of these important plant and human pathogens and also as potential targets for development of drugs/agents that specifically target these bacteria.