Brazil’s Atlantic Forest biome is currently undergoing forest loss due to repeated episodes of devastation. In this biome, bees perform the most frequent pollination system. Over the last decade, network analysis has been extensively applied to the study of plant–pollinator interactions, as it provides a consistent view of the structure of plant–pollinator interactions. The aim of this study was to use palynological studies to obtain an understanding of the relationship between floral visitor bees and the pioneer plant S. didymum in a fragment of the Atlantic Forest, and also learn about the other plants that interact to form this network. Five hundred bees were collected from 32 species distributed into five families: Andrenidae, Apidae, Colletidae, Megachilidae, and Halictidae. The interaction network consisted of 21 bee species and 35 pollen types. The Solanum-type bee species with the highest number of interactions were Anthrenoides sp. 1, Augochlora sp. 2, and Augochloropsis notophos, representing 71.78% of their interactions. Augochloropsis notophos and Augochlora sp. 2 were the only common species in the flowers of S. didymum. Given the results of our study, we conclude that Solanum is an important source of pollen grains for several native bee species, mainly for the solitary species that are more diverse in the south of Brazil. Moreover, our results indicate that bees from the families Halictidae (A. notophos, Augochlora) and Andrenidae (Anthrenoides) are the pollinators of S. didymum.