Bacteria of the genus Sodalis live in symbiosis with various groups of insects. The best known member of this group, a secondary symbiont of tsetse flies Sodalis glossinidius, has become one of the most important models in investigating establishment and evolution of insect-bacteria symbiosis. It represents a bacterium in the early/intermediate state of the transition towards symbiosis, which allows for exploring such interesting topics as: usage of secretory systems for entering the host cell, tempo of the genome modification, and metabolic interaction with a coexisting primary symbiont. In this study, we describe a new Sodalis species which could provide a useful comparative model to the tsetse symbiont. It lives in association with Melophagus ovinus, an insect related to tsetse flies, and resembles S. glossinidius in several important traits. Similar to S. glossinidius, it cohabits the host with another symbiotic bacterium, the bacteriome-harbored primary symbiont of the genus Arsenophonus. As a typical secondary symbiont, Candidatus Sodalis melophagi infects various host tissues, including bacteriome. We provide basic morphological and molecular characteristics of the symbiont and show that these traits also correspond to the early/intermediate state of the evolution towards symbiosis. Particularly, we demonstrate the ability of the bacterium to live in insect cell culture as well as in cell-free medium. We also provide basic characteristics of type three secretion system and using three reference sequences (16 S rDNA, groEL and spaPQR region) we show that the bacterium branched within the genus Sodalis, but originated independently of the two previously described symbionts of hippoboscoids. We propose the name Candidatus Sodalis melophagi for this new bacterium.