Just because you've never been to them doesn't mean you've never been to them.
It's usually nothing to worry about.
Certainly, malware is a possibility. I'll also call out "foistware" or Potentially Unwanted Programs (PUPs) -- software that appears on your system unexpectedly after installing something else.
However, there are many more benign scenarios. It's possible your browser may simply be doing a good job protecting you.
Become a Patron of Ask Leo! and go ad-free!
Sites in my history I've never been to
Sites can appear in your browsing history due to malware, blocked pop-ups and pop-unders, webpages built from other webpages, and browser pre-fetch features. With the exception of malware, most are benign.
Malware
Malware sometimes works by forcing your browser to go places you would never go. Potentially Unwanted Programs (PUPs) in particular can add toolbars and other software to your system that intercept what you're doing and just rudely take over, sending you to bogus search sites or worse.
These days, my first recommendation when you run into unexpected history entries is to make sure your machine has no malware. In particular, I suggest you run the tools outlined in How Do I Remove PUPs, Foistware, Drive-bys, Toolbars, and Other Annoying Things I Never Wanted?
Pop-ups and pop-unders
Many websites employ pop-ups: additional browser windows that open when you visit the site. These often contain ads for which the site owner gets paid.
Pop-unders are similar, though they've fallen out of favor in recent years. They are additional browser windows created when you visit a site that are placed behind your current browser window so they'll be visible when you minimize or exit the browser.
Pop-up blockers -- now built into most browsers -- keep pop-up and pop-under windows from displaying. The blockers intercept the requests to create new browser windows and prevent them from opening.
My theory is that the URLs behind blocked pop-ups sometimes still appear in your history because they were added to the list before the pop-up was blocked. You've never seen the site, but it's there in the list.
One page, many sources
Some webpages look like a single page but are actually a composite of more than one page or page fragments. What you see as a single URL may have fetched content from several different sites.1
Depending on how your browser handles these requests, it's possible that these page elements appear as individual entries in your history. You wouldn't recognize them because they're not pages you explicitly visited, but they're present because they were part of some page you did go to.
Browser pre-fetch
Many web browsers now include a feature where they begin fetching the pages linked to in the page you're currently viewing.
When you click a link on the page, if all or even some of it has already been downloaded, it comes up much more quickly. That there's downloading going on you didn't explicitly ask for is typically not an issue because you're busy reading the page you originally requested.
Once again, whether these pages appear in the browser history depends on the browser. In theory, I'd only expect the links you actually clicked or pages you actually viewed to appear, but browser designers could decide otherwise.
Most of the time, this pre-load feature is something you can turn off in the options for the browser you use.
Do this
Ultimately, unless someone else is using your computer when you're not looking -- which is also something worth checking for -- this issue is typically harmless and benign.
However, that shouldn't stop you from taking appropriate precautions to keep your computer safe.
Put me in your history! Subscribe to Confident Computing: less frustration and more confidence, solutions, answers, and tips in your inbox every week.
Podcast audio
Related Video
Footnotes & References
1: I do a variation of this myself. Many of the images I display come from a completely different domain or "site".
Closed comments since most comments were nothing more than questions answered by the article. PLEASE read the article.