The species from the order Neisseriales are currently distinguished from other bacteria on the basis of branching in 16S rRNA gene trees. For this order containing a single family, Neisseriaceae, no distinctive molecular, biochemical, or phenotypic characters are presently known. We report here detailed phylogenetic and comparative analyses on the 27 genome sequenced species of the order Neisseriales. Our comparative genomic analyses have identified 54 conserved signature indels (CSIs) in widely distributed proteins that are specific for either all of the sequenced Neisseriales species or a number of clades within this order that are also supported by phylogenetic analyses. Of these CSIs, 11 are specifically present in all of the sequenced species from this order, but are not found in homologous proteins from any other bacteria. These CSIs provide novel molecular markers specific for, and delimiting, this order. Twenty-one CSIs in diverse proteins are specific for a group comprised of the genera Neisseria, Eikenella, Kingella, and Simonsiella (Clade I), which are obligate host-associated organisms, lacking flagella and exhibiting varied morphology. The species from these genera also formed a strongly supported clade in phylogenetic trees based upon concatenated protein sequences; a monophyletic grouping of these genera and other genera displaying similar morphological characteristics was also observed in the 16S rRNA gene tree. A second clade (Clade II), supported by seven of the identified CSIs and phylogenetic trees based upon concatenated protein sequences, grouped together species from the genera Chromobacterium, Laribacter, and Pseudogulbenkiania that are rod-shaped bacteria, which display flagella-based motility and are capable of free living. The remainder of the CSIs were uniquely shared by smaller groups within these two main clades. Our analyses also provide novel insights into the evolutionary history of the Neisseriales and suggest that the CSIs that are specific for the Clade I species may play an important role in the evolution of obligate host-association within this order. On the basis of phylogenetic analysis, the identified CSIs, and conserved phenotypic characteristics of different Neisseriales genera, we propose a division of this order into two families: an emended family Neisseriaceae (corresponding to Clade I) containing the genera Alysiella, Bergeriella, Conchiformibius, Eikenella, Kingella, Neisseria, Simonsiella, Stenoxybacter, Uruburuella and Vitreoscilla and a new family, Chromobacteriaceae fam. nov., harboring the remainder of the genera from this order (viz. Andreprevotia, Aquaspirillum, Aquitalea, Chitinibacter, Chitinilyticum, Chitiniphilus, Chromobacterium, Deefgea, Formivibrio, Gulbenkiania, Iodobacter, Jeongeupia, Laribacter, Leeia, Microvirgula, Paludibacterium, Pseudogulbenkiania, Silvimonas, and Vogesella).