1590s, "belonging to another country," from French exotique (16c.) and directly from Latin exoticus, from Greek exotikos "foreign," literally "from the outside," from exo "outside" (see exo-). Sense of "unusual, strange" in English first recorded 1620s, from notion of "alien, outlandish." In reference to strip-teasers and dancing girls, it is attested by 1942, American English.
Exotic dancer in the nightclub trade means a girl who goes through a few motions while wearing as few clothes as the cops will allow in the city where she is working ... [Life magazine, May 5, 1947]
As a noun from 1640s, "anything of foreign origin," originally plants.