Sandfly-transmitted phleboviruses, such as Toscana, sandfly fever Sicilian, and sandfly fever Naples, can cause human disease and circulate at high rates in Mediterranean countries. Previous studies have also established that viruses other than phleboviruses may be detected in and isolated from sand flies. The recent detection and isolation (in a large variety of mosquito species) of insect-only flaviviruses related to cell fusing agent virus has indicated that the latter is not an evolutionary remnant but the first discovered member of a group of viruses, larger than initially assumed, that has high genetic heterogeneity. Insect-only flaviviruses have been detected in and/or isolated from various species of mosquitoes, but nevertheless only from mosquitoes to date; other dipterans have not been screened for the presence of insect-only flaviviruses. The possible presence of flaviviruses, including insect-only flaviviruses, was investigated in sand flies collected around the Mediterranean during a trapping campaign already underway. Accordingly, a total of 1508 sand flies trapped in France and Algeria, between August 2006 and July 2007, were tested for the presence of flaviviruses using a PCR assay previously demonstrated experimentally to amplify all recognized members of the genus Flavivirus, including insect-only flaviviruses. Two of 67 pools consisting of male Phlebotomus perniciosus trapped in Algeria were positive. The two resulting sequences formed a monophyletic group and appeared more closely related to insect-only flaviviruses associated with Culex mosquitoes than with Aedes mosquitoes, and more closely related to insect-only flaviviruses than to arthropod-borne or to no-known-vector vertebrate flaviviruses. This is the first description of insect-only flaviviruses in dipterans distinct from those belonging to the family Culicidae (including Aedes, Culex, Mansonia, Culiseta, and Anopheles mosquito genera), namely sand flies within the family Psychodidae. Accordingly, we propose their designation as phlebotomine-associated flaviviruses.