The apoid fauna of Bulgaria is considered one of the richest in Europe. However, despite the numerous sampling efforts over the last century, it remains insufficiently studied and a clear overview of its diversity and the ecology of species present is lacking. This lack of understanding is further exacerbated by the changing climate, which continually alters the northern and southern limits of species distributions, especially in the warm southern parts of the country. In this study, the megachilid and colletid fauna of a dry sub-Mediterranean steppe habitat were surveyed using standardized transect walks, whereby all bees belonging to the two families were collected, and their floral visits were recorded. Flower abundance was noted during each survey, and pollen was taken from the identified species for a reference collection. A total of 76 plant and 31 bee species were observed, with 45 individual plant–pollinator associations being identified at a species level. The most visited plants were the flowers of Centaurea salonitana Vis. (six species), Eryngium campestre L. (four species), Ajuga chia Schreb. (four species), Ornithogalum montanum Cirillo (three species), Onobrychis arenaria (Kit.) DC. (three species) and Knautia arvensis (L.) Coult. (three species). Two species, Hoplitis pici (Friese, 1899) and Megachile semicircularis van der Zanden, 1996, are reported as new for Bulgaria, and twenty-two species are new for the locality. Considering the relative popularity and available historical data from the study location, the Besapari Hills, these results reconfirm the apoid fauna of the country as severely understudied, furthermore accentuating the need for a comprehensive pollinator monitoring in Southern Europe.