Almost 200 species of orchid bees are the exclusive pollinators of nearly 700 specialized orchids in the Neotropics. This well-known mutualism involves orchids, called perfume orchids, which produce species specific blends of floral fragrances, and male orchid bees, which collect and use these fragrance compounds during their courtship. We report here the naturalization of an orchid bee, Euglossa viridissima, in southern Florida, where perfume orchids are absent. Chemical analysis of the contents of the fragrance storage organs in the hind tibias of 59 male bees collected in Florida identified 55 fragrance compounds, including 27 known from the perfumes of 9 species of E. viridissima’s orchid mutualists in MesoAmerica. Aromatic leaves, such as basil, were found to be important surrogate sources of needed fragrance compounds in Florida. The bee’s ability to live and become abundant in the absence of its orchid mutualists suggests that the orchid bee-perfume orchid mutualism may be facultative for the bees, even though it is obligatory for the orchids. This invasive bee visits and potentially pollinates the flowers of many plants in Florida, behavior that could promote the abundance of selected exotic and native species.