Haemoproteus (Parahaemoproteus) parasites are transmitted by Culicoides biting midges. However, the natural vectors of only six of the almost 180 recognized Haemoproteus species have been identified. The aim of this study was to investigate wild biting midges naturally infected with Haemoproteus and to understand the interaction network between Culicoides and Haemoproteus in Europe. Culicoides were collected with UV light traps from different sites in Lithuania. Parous females were morphologically identified based on their wings and heads. PCR-based methods were used to detect the Haemoproteus DNA, and salivary gland preparations were analyzed for the presence of sporozoites. Of the 580 Culicoides analyzed, 5.9% were positive for Haemoproteus DNA, and sporozoites were found in two of 11 sampled biting midge species: Culicoides kibunensis and Culicoides segnis. The interaction network revealed that C. kibunensis and C. segnis are frequently associated with several Haemoproteus lineages. On the other hand, some Haemoproteus lineages were found to interact with only one Culicoides species. This was the first report of C. segnis being a competent vector for H. minutus TURDUS2, H. asymmetricus TUPHI01, H. majoris PHSIB1, and H. fringillae CCF3; and of C. kibunensis being a competent vector for H. belopolskyi HIICT1. Culicoides segnis and C. kibunensis are both important vectors of Haemoproteus parasites.