This lies not only in the multitude of authors from one genre who've moonlighted in the other — or have even been completely ambidextrous — but also in the many works that share traits from either side of the divide. This can be the "sword & planet" stories of Edgar Rice Burroughs and his successors, the epic fantasy in space of Stars Wars, or the far more complicated blends of authors such as Michael Moorcock.
The confusion starts early, partly due to the difficulty in defining what should actually count as fantasy or science fiction before a couple of centuries ago. Fantasy seems more straightforward. A large proportion of older literature, from Homer to Shakespeare, deals with magic and the supernatural, but it's not always easy to tell how much of this would have been viewed at the time as fantasy.
That's certainly not to say that all ancient cultures were naïve, but they'd certainly have viewed these matters differently from modern western civilisation. The only stories we know for certain was treated as fantasy were the mediaeval Icelandic sagas of the gods and heroes, because they had a word for them: "lying sagas", as opposed to the "true-seeming sagas", covering both biography and historical fiction. It's likely, though, that many other cultures, from Greece to China, were perfectly aware of when they were letting their fancies roam.
Early science fiction has the opposite problem, where we need to appreciate that some absurdly fanciful ideas might at the time have qualified as sophisticated science. For instance, the 2nd century AD author Lucian of Samosata wrote an adventure story where his heroes at one point visited the Moon and met its inhabitants. To us, there seems little science in this, but it should be remembered that, in Lucian's day, the mere concept of the celestial bodies being worlds that might be inhabited was pretty cutting edge.
Although it's a slight oversimplification, it could be argued that modern fantasy began in 1786 with William Beckford's Vathek and modern science fiction in 1818 with Mary Shelley's Frankenstein; or the Modern Prometheus. The first crossover I'm aware of came in 1858, in George MacDonald's Phantastes, a strange, allegorical fantasy. In the middle of its hero's wanderings, he finds the library of a great palace where he "experiences" (rather than reads) various tales. One is set on a planet with such a long orbit around its sun that no-one experiences more than one or two seasons.
Like Lucian, MacDonald's scientific accuracy might be doubted today, but no more than some of Wells's ideas, and he was using genuine scientific speculation to create his story. Part of MacDonald's legacy was a small but interesting subgenre of allegorical science fantasy, such as David Lindsay's A Voyage to Arcturus and C. S. Lewis's space trilogy.
One of the subgenres that most obviously combines Sf and fantasy is the Dying Earth genre. The earliest examples of this, such as Shelley's The Last Man and Wells's The Time Machine, were unmistakably SF, but starting with William Hope Hodgson's 1912 The Night Land, various dying earths (notably by Clark Ashton Smith and Jack Vance, and more recently Gene Wolfe) combined elements of fantasy or horror with the undeniable SF concept of the planet's days being numbered. Smith and Vance, for instance, both assumed that a decadent last civilisation would rediscover magic to replace science.
Perhaps the great era for genre-blending came with the pulp magazines in the 1930s and 1940s. The great Weird Tales authors slipped a little SF into the mix. H. P. Lovecraft's tale Through the Gate of the Silver Key, for instance, combined horror, fantasy and SF, while Clark Ashton Smith, normally teetering between fantasy and horror, wrote a few SF stories, including the concept of time travel in which the time machine stays still and the universe moves on, allowing the time-travellers to encounter a series of planets. I suspect Einstein would beg to differ, but it's still an interesting concept.
When John W. Campbell started Unknown (also known as Unknown Worlds) he persuaded many of the science fiction authors he'd nurtured in Astounding Science Fiction to try their hand at fantasy. Perhaps the defining series in Unknown * was the Harold Shea stories of Fletcher Pratt and L. Sprague de Camp. This used the developing concept of alternative worlds, which would ultimately grow into the theory of the multiverse, to assume that it was possible to travel to fictional "worlds" such as the Norse myths and The Faerie Queen. A similar concept was used later by Andre Norton (also an "ambidextrous" author) to transport her hero in the first chapter of her Witch World series.
Authors like Pratt and de Camp combined genres not only by providing a scientific framework for their fantasy tales, but also by approaching the fantasy elements with the rigour of SF. Shea and his associates, for instance, have to work out the laws by which magic and the supernatural work in the various worlds they visit. The approach is summed up by the title of one of the stories: The Mathematics of Magic.
Unknown's brief span on this earth was… well, brief, regrettably, but many of his SF authors (including Robert Heinlein, for instance) continued to write occasional fantasy. Vance and Anderson, for instance, were both too late for Unknown but wrote works very much in its tradition. The great number of later writers who've combined SF and fantasy careers (sometimes combining them in ways that can't be easily unpicked) include ** Andre Norton, Michael Moorcock, Ursula LeGuin, Marion Zimmer Bradley, Anne McCaffery, George R. R. Martin, and my personal favourite, Mary Gentle.
Most of the time, it's easy enough to tell what's fantasy and what's science fiction. It's unlikely that anyone would mistake I, Robot for fantasy or Lord of the Rings for SF ***. There's a substantial grey area between them, though. As we've seen, authors including Pratt & de Camp, Anderson, Moorcock and Norton — arguably even C. S. Lewis — used the scientific theory of the multiverse as a mechanism to get their characters to their fantasy worlds, although in Moorcock's case it's a lot more than just a mechanism.
Science fiction can be "infected" with fantasy just as much as the reverse. McCaffery's Pern novels are ultimately SF, since we gradually learn that Pern is a colonial planet and the mysterious elements like dragons and thread-fall have scientific explanations, but for the most part the characters themselves aren't aware of any of this, and the books read more like fantasy.
Iain M Banks (whose "mainstream" novels as Iain Banks include a couple of fantasies) pulled off a similar trick in Inversions, where two characters from his technologically advanced Culture visit a planet with a Renaissance-level civilisation. The story is told entirely from the point of view of the planet's natives, so the visitors' technology appears to be magic, and it's only the reader's privileged knowledge that lets us know what's really going on.
Then again, speculative fiction can be the most glorious mash-up that shows no respect whatsoever for genre. Mary Gentle's Rats & Gargoyles is one such. Described by the author as "Hermetic Science Fiction" (in other words, suppose the laws of nature really were as the Renaissance mystics assumed them to be) it has everything from a standard fantasy Thieves Guild to trains and airships. It also has an East Pole (presumably stolen from Winnie the Pooh) and five cardinal points of the compass, each at right angles to the other. Strangely, she doesn't provide a map.
In the end, the job of a story is to entertain, excite and possibly educate, not to toe a genre line. While there's nothing at all wrong with writing a good story that stands four-square within a genre, the borderlands can often provide the most fertile territory, and natives of one land can learn from those who do things differently in another country.
Fantasy has explored excellent borders with horror, with historical fiction, and sometimes even with realism, but there's something about the combination of fantasy and science fiction that seems entirely appropriate. Perhaps that's why they almost always share a section in bookshops and libraries.
* Arguably the greatest series to appear in Unknown was Fritz Leiber's tales of Fafhrd and the Gray Mouser, but this was somewhat atypical. Campbell accepted them with comments like "This is more of a Weird Tales piece than Unknown usually prints. However—" The missing sentence presumably being something along the lines of "However, who cares with a story this good?"
** Apologies if I haven't included your favourite. It really is a very great number. Feel free to add any glaring omissions below.
*** You'd think. In fact, a review in 1954 by Naomi Mitchison (who wrote fantasy herself) describes Lord of the Rings as "really super science fiction". Go figure.