Anything by Tangerine Dream, October Project or Jean Luc Ponty. Also, the song, “Emotion in Motion,” by Rik Ocasek is quite evocative and the video is pure fantasy.
Ritchie Blackmore’s Blackmore’s Night
Sounds like you’re looking for albums that take you away to another, at least slightly unreal or imaginary, place.
Some of Van Dyke Parks’s albums, such as Orange Crate Art (with Brian Wilson) and Jump! might do the trick.
Some of XTC’s other albums might also qualify (Skylarking? Big Express?—though that one’s less pastoral and more sooty-English-town).
The Decemberists have at least a couple songs that take you away to the world of old sea chanties.
Darn Floor - Big Bite by Daniel Amos is an amazing, otherworldly album.
I second El Dorado, and some Moody Blues and Alan Parsons Project. But
has always struck me as the kind of homage to Tolkien someone would write if they knew nothing about The Lord of the Rings beyond its title and the fact that it is fantasy.
I’m with you there.
Hawkwind performed many songs based on and in collaboration with fantasy writer Michael Moorcock. Their Chronicle of the Black Sword is based on Moorcock’s Elric of Melniboné novels.
That’s a really great way to put it. I struggled to describe this idea in a way that wouldn’t just net me a list of heavy metal albums with wizards on the cover. 
Thanks for the suggestions all.
I’m assuming you are familiar with early Genesis. Specifically, The Lamb Lies Down on Broadway?
Black Sabbath has a song called “The Wizard”.
Also Ironman, War Pigs and Heaven & Hell of course but those are very dark fantasy worlds that they evoke.
I was going to suggest the albums “Songs from the Woods” or “Broadsword and the Beast”.
On the album cover of the latter (according to wiki);
If you want an album that looks the part too that is.
Try some Electric Wizard if you want some really really deep heavy stoner music.
Lots of Finnish rock bands seem take inspiration from fantasy. Nightwish is the most successful
of the fantasy rock genre. Not my cup of tea though.
This song is about LOTR.
These are a bit more generic fantasy. Link. Link.
Loreena McKennitt. A lot of her stuff has a medieval/fantasy feel to it.
Tubular Bells by Todd Rundgren 
Let me have a link - I thought my Mike Oldfield collection was complete.
silenus mentioned Mike. Hergest Ridge is a nice pastoral, somewhat on the model of Beethoven’s Sixth Symphony. Ommadawn is also a good choice - the beginning of the second side, with one million guitars, is very otherworldly. While I’m not all that fond of his Voyager (no relation) I think it would fit the bill. Incantations is pretty nice also.
I prefer Tubular Bells II to Tubular Bells - it has some songs named after Arthur C. Clarke stories, including Sentinel and Sunjammer. To prove this is not a coincidence, Songs of Distant Earth is based on Clarke’s book of the same name, and has a track of the Sun going nova.
Black Blade by Blue Oyster Cult was a great fantasy song, and Michael Moorcock (author of the Eternal Champion series) co-wrote the lyrics.
Much of Rick Wakeman’s solo work carries fantasy themes. He did a Lord of the Rings tribute album that’s all instrumental that’s very pastoral and highly evocative.
I’ll second Jethro Tull (especially The Broadsword and the Beast) and Pink Floyd.
If you’re looking for Renaissance, the lineup changed dramatically over the years, and one of the ex-members released some stuff under the Renaissance name in the 1990s. Look for the stuff from the early 1970s with Annie Haslam and John Tout, especially the albums Prologue and Scheherazade and Other Stories.
Pink Floyd has a huge variety of work, some of which fits your category. If you haven’t heard it, you MUST run out and get the song, Several Species of Small Furry Animals Gathered Together in a Cave and Grooving With a Pict. If that doesn’t form mental pictures for you, nothing will. I’m not sure if they’ll be the mental pictures you want, but that’s another story.
Man, I haven’t listened to Tangerine Dream in decades. I’ll have to go find some.
Good luck - report back on what you compile!
Which album? I love Yes and Journey to the Center of the Earth (which might qualify) but I don’t even know about the LotR tribute.
I have it listed as Songs of Middle Earth: A Tribute to The Lord of the Rings.
“In the Court of the Crimson King” by King Crimson.
“Stonehenge” by Spinal Tap.
Autumn Almanac, you may find some more songs you like in this thread:
http://boards.straightdope.com/sdmb/showthread.php?t=474834&highlight=farewell+kings
Black Sabbath’s “Heaven and Hell”.
Kiss - “Music from the Elder”. One of the strangest albums they released, this doesn’t sound anything like the Kiss we all know and love (or hate). Some really good songs, and quite underrated, IMHO.
**Ayreon ** - A musician from Holland who does these amazing sci-fi concept albums, plays most of the music himself, then gets singers from bands he likes to come in and do the vocals. “Into the Electric Castle” is one of my favorite albums of all time. It’s the story of 8 people plucked from random times/places in history and placed in a mysterious place for unknown purposes. It’s just amazing. Music is mainly hard rock, 70’s style, with a little acoustic and electronic thrown in. Side note: He also released an album under the name Star One, on which each song was based on a different Sci Fi movie (The Abyss and Star Wars to name two).
Rhapsody of Fire - Italian power metal band with an epic fantasy story. There’s 6 or 7 albums, each one is a different chapter in the same story. A warrior fights to protect his land and people from evil. Aside: Christopher Lee (who played Saruman in Lord of the Rings and Count Dooku in Star Wars) does the narration on some of their more recent stuff. Recommended: “Symphony of Enchanted Lands”, “Power of the Dragonflame”. Style: Fantasy rock/metal.
Lana Lane - More fairy tale than medieval fantasy, most songs are either ballads or catchy rock tunes. Her voice has been compared to Ann Wilson from Heart and Stevie Nicks. Recommended albums: “Winter Sessions”, “Queen of the Ocean”. Style: Prog Rock note: LL has said they hate the term “prog rock”, and are opting to use “symphonic rock” instead, which makes even less sense since there’s no symphony.
Blind Guardian - Thrash metal fantasy band from Germany. Until the last couple albums, almost every song was Lord of the Rings related. Recommended album: “Nightfall in Middle Earth”, which was based on the Silmarillion. Style: JRR Tolkien meets a thrash metal band.
Hammerfall - I believe these guys are from Germany. They’re pretty much the same style as Rhapsody or Blind Guardian. Recommended album: “Renegade”. Style: Melodic power metal.
**Dragonland **- I forget where these guys are from, but they’re another Euro style fantasy metal band. A bit heavier and faster than most. Recommended album: “Holy War”. Style: fast thrash metal.
Glass Hammer - This band is pretty mellow, most of the stuff I’ve listed is rock/metal. They have an album called, appropriately enough “The Middle Earth Album”, that wouldn’t sound out of place in a tavern in Hobbiton. They also did one based on CS Lewis’ “Perelandra” series, and one “Chronometree” about a guy obsessed with concept albums. Recommended album “The Middle Earth Album”. Style: Folk/Celtic folk/light rock
**Colonel Jeffery Pumpernickel: A Concept Album **- Not actually a band, CJP was a concept album featuring exclusive songs from a bunch of indie bands like Guided by Voices and the Black Heart Procession. Not sure if this qualifies as fantasy for the OP, but this is just one of the flat out strangest albums and storylines I’ve ever heard. The storyline is too strange to sum up shortly, lets just say it involves the Colonel and his strange fantasies about a childhood fever, hallucinations, a Nurse, his military career, and underwater fire battles. Recommended album: “Colonel Jeffery Pumpernickel: A Concept Album” (there’s only the one). Style: Indie Rock.