I would expect that it's post-Einstein, but probably not by too much. I know that Star Trek used it to death, but I suspect that it pre-dated ST.
Earliest instances of the term "space-time continuum"
The earliest use of the full term "space-time continuum" that I can seem to find is by H.P. Lovecraft in the story "The Whisperer in the Darkness" written February-September 1930 and first published in Weird Tales, August 1931. It contains the following passage:
The blasphemies which appeared on earth, it was hinted, came from the dark planet Yuggoth, at the rim of the solar system; but this was itself merely the populous outpost of a frightful interstellar race whose ultimate source must lie far outside even the Einsteinian space-time continuum or greatest known cosmos.
I can find two other instances of the term in H.P. Lovecraft stories from the same era. "At the Mountains of Madness" written a year later (Feb/Mar 1931), though not published until 1936 (after being rejected by Weird Tales in 1931) has
The Old Ones, but for their abnormal toughness and peculiar vital properties, were strictly material, and must have had their absolute origin within the known space-time continuum; whereas the first sources of the other beings can only be guessed at with bated breath.
Finally, the term makes two appearances in "The Dreams in the Witch-House" written April/March 1932 and published in the July 1933 issue of Weird Tales. (All of these are available online for free here.)
(Much) Earlier Conceptualization of Space-time in Literature
I should mention, however, that the notion of space and time be a single linked entity (though not using the literal phrase "space-time continuum") is quite old: much older than Einstein's relativity or Minkowski's space-time.
From the wikipedia article on space-time we have the following historical literary instances of space and time being linked:
Incas regarded space and time as a single concept, referred to as pacha (Quechua: pacha, Aymara: pacha). The peoples of the Andes maintain a similar understanding.
The idea of a unified spacetime is stated by Edgar Allan Poe in his essay on cosmology titled Eureka (1848) that "Space and duration are one". In 1895, in his novel The Time Machine, H. G. Wells wrote, "There is no difference between time and any of the three dimensions of space except that our consciousness moves along it", and that "any real body must have extension in four directions: it must have Length, Breadth, Thickness, and Duration".
Marcel Proust, in his novel Swann's Way (published 1913), describes the village church of his childhood's Combray as "a building which occupied, so to speak, four dimensions of space—the name of the fourth being Time".
The first fictional work to use the term "space-time continuum" may be the 1927 novel Now East, Now West by Susan Ertz, described by book dealers (presumably from dust jacket blurb) as:
"An absorbing story of married life. It tells of the pretty and popular Althea Goodall, who is happily if not romantically married, and of her being transplanted from America to English social circles."
Apparently not science fiction, but that wasn't a requirement. The online OED's earliest citation for the phrase "space-time continuum" is from this book:
1927 S. Ertz Now East, now West viii. 117 I've got quite drunk on theories about the space-time continuum.
Expanding on @Bamboo 's discussion of "the notion of space and time [as] a single linked entity", mention of space and time as similar or linked concepts in English may go back much further than 1848. Consider the following:
35: But nathelees, whil I have tyme and space,
36: Er that I ferther in this tale pace,
37: Me thynketh it acordaunt to resoun
38: To telle yow al the condicioun
Source: Chaucer's Canterbury Tales, Prologue, 14th century.
But nonetheless, while I have time and space,
Ere (before) I pace (step) further in this tale,
I think it to be in accord (agreeable) to reason (decide)
To tell y'all the condition...
We can't tell, based on this passage, whether Chaucer really thought of space and time in the modern sense of a space-time continuum or whether he just happened to juxtapose these concepts for another reason. The proximity of the concepts here, however, is significant evidence that the ideas were at least seen as related or compatible in some way.