Etymonline tells us about this sense of chemistry:
c.1600, "alchemy" (see chemical); the meaning "natural physical process" is 1640s, and the scientific study not so called until 1788. The figurative sense of "instinctual attraction or affinity" is attested slightly earlier, from the alchemical sense.
Alchemy was chemistry in its infancy, and might refer to something that seemed to be magic. These definitions are pertinent:
The causing of any sort of mysterious sudden transmutation.
Any elaborate transformation process or algorithm.
Chemistry between two people is an unexplained reaction, and it came first, before our understanding of the science of chemistry.