Here we describe the new trypanosomatid, Phytomonas borealis sp. n., from the midgut of the spiked shieldbugs, Picromerus bidens (Linnaeus), collected in two locations, Novgorod and Pskov Oblasts of Russia. The phylogenetic analyses, based on the 18S rRNA gene, demonstrated that this flagellate is a sister species to the secondary monoxenous Phytomonas nordicus Frolov et Malysheva, 1993, which was concurrently documented in the same host species in Pskov Oblast. Unlike P. nordicus, which can complete its development (including exit to haemolymph and penetration into salivary glands) in Picromerus bidens, the new species did not form any extraintestinal stages in the host. It also did not produce endomastigotes, indispensable for transmission in other Phytomonas spp. These observations, along with the fact that P. bidens overwinters at the egg stage, led us to the conclusion that the examined infections with P. borealis were non-specific. Strikingly, the flagellates from the Novgorod population contained prokaryotic endosymbionts, whereas the parasites from the second locality were endosymbiont-free. This is a first case documenting presence of intracellular symbiotic bacteria in Phytomonas spp. We suggest that this novel endosymbiotic association arose very recently and did not become obligate yet. Further investigation of P. borealis and its intracellular bacteria may shed light on the origin and early evolution of endosymbiosis in trypanosomatids.