The idea of "possible worlds" or something like it certainly isn't new. One extremely famous example is Leibniz's concept of the "greatest possible world" that still gets thrown around in philosophy of religion discussions. Basically, the idea is that there were a number of different "worlds" God could have created. Leibniz reasoned that, of all these possibilities, God necessarily created the "best" or "greatest" one, which in turn implies that there is no unnecessary evil in the world. This, of course, would mean that the equally famous "problem of evil" argument against God's existence would fail, since that argument relies on the eminently plausible assumption that there is lots of unnecessary evil in the world (the holocaust, natural disasters, etc).

A similar point is hinted at in Descartes, who uses the idea of "possible worlds" in The World as his central conceit. His idea was to avoid any complications from the "truths" of revelation in his physics. Instead, he posited a world much like our own, with the exception that God never miraculously intervenes or anything like that. Instead, God just creates matter and lets it develop naturally. Descartes then uses this possible world to deduce natural laws (such as the conservation of motion) and even claims in another text, Discourse on Method, that even if God had created many worlds there could be none in which these laws would fail to be observed.

Now, a key point here is that Leibniz and Descartes were not thinking of these possible worlds as actual, whereas today you do often here folks thinking in those terms. Parallel universes are sometimes thought, not merely to be possible universes, but actual ones that are somehow isolated from our own. This is very often associated with either science (probably in reference to very recent work in theoretical physics) or, more commonly, in science fiction. However, philosophers still have a related concept that goes back at least to the work of David Lewis, especially a book he published in the 80's called On the Plurality of Worlds. Very roughly, in that book, he defends the idea that all possible worlds are actual, causally isolated worlds and that, moreover, it is only in reference to such actual "parallel" worlds that we can make sense of counterfactuals like "If I throw the stone, the window would break." His idea is that we evaluate this statement in reference to a "nearby" possible world in which I did throw the stone. If, at that world, the window broke, then the statement is true; otherwise, it is false. This is naturally extremely controversial, and the consensus, then and now, is that he was wrong about this.

So the upshot is that there is a long history in philosophy of talking about "possible worlds" that are similar to our own but different in some way that makes some interesting point. So it wouldn't be totally inconceivable to hear a philosopher at least as far back as the early modern period saying things like "In some possible world, X is different. What would this entail? What does this tell us about X?" This sort of talk isn't too different from the "parallel universe" examples you describe, though honestly I've no idea if this sort of talk permeated into ordinary language the way parallel universe talk has today.

The modern conception of parallel worlds arises from Quantum physics. It wasn't until sci fi writers started running with the concept that did the idea enter into the mainstream.