And the Band Played Waltzing Matilda. The only version I’ve heard is by The Pogues, but theirs is good.
Warren Zevon had numerous ‘story songs’, and they’re just fantastic.
Among his best:
Carmelita
Veracruz
Jeannie Needs a Shooter
The French Inhaler
Desperados Under the Eaves
Hit Somebody! (The Hockey Song)
Boom Boom Mancini
Lawyers, Guns and Money
Frank and Jesse James
Mama Couldn’t be Persuaded
Roland the Headless Thompson Gunner
Another source of great story songs is John Prine Some of his best:
Sam Stone
Donald and Lydia
Paradise
The Great Compromise
Christmas in Prison
Hello in There
Angel from Montgomery
Six O’clock News
Mexican Home
Lake Marie
Oooo, I’ll have to check that one out. Tell you what, I’ll go find the Nelson/Cash/Jennings version and you go dig up the Phil Ochs one. You’ll thank me. Honest. While you’re at it, you might also want to find Tam Lin by Fairport Convention and Alison Gross by Steeleye Span. Both of them have supernatural storylines and great melodies.
Oh, and Lorenna McKennitt, who I maligned up-thread, has a beautiful version of Alfred Lord Tennyson’s Lady of Shalott.
The Irish Ballad by Tom Lehrer 
Ron Hynes, Ron Hynes RON HYNES!!
and youtube link
Lovely, urgent, haunting - and butchered. At least Loreena McKennit only cut two verses (Though one of them is essential to the plot).
See if you can find the late, great Peter Bellamy’s albums of Kipling poems set to music: Merlin’s Isle of Gramarye and Oak, Ash and Thorn are songs from ‘Rewards and Fairies’ and ‘Puck of Pook’s Hill’, The Barrack-Room Ballads of Rudyard Kipling does what it says on the tin and *Keep on Kipling * and Mr Kipling Made Exceedingly Good Songs are settings of general Kipling poetry. All are done in the folk tradition (some to traditional tunes) and are well worth a listen. Difficult to find, though.
And don’t forget The Blacksmith of Brandywine, by Pat Garvey. A filk favorite – whether it’s based on a true story, as alleged, I do not know.
On a lighter note: Cows With Guns, by Dana Lyons. Which is based on a true story. Is too!
As a bluegrass fancier, for 30 years now, I can heartedly suggest Knoxville Girl.
Sad, but true, mean sumbitches existed in the old days. If you want to hear the best version, it would be by the Stanley Bros.
I don’t know. Seems a bit far fetched. I bet they just inflated it from this incident.
“Springhill Mining Disaster” by Pete Seeger (recorded by The Dubliners among others) is a story song and a good one, IF you get one of the long versions. Please ignore the gutted U2 version.
As others have said above, you can’t go far into traditional Irish and Scottish music, or music influenced by these traditions, without bumping into ballads galore. Some are centuries old and exist in multiple versions and recordings. “Little Musgrave” and “Barbara Allen” are love stories gone awry, “Barratt’s Privateers” and “Greenland Whale Fisheries” are tales of work gone wrong, and there are lots of battle songs, some historically reliable, many not.
Even The Pogues’ “Smell of Petroleum” could count as a story song, of a sort. --That opens up the topic of comic ballads, a genre in itself. Traditional ones include “The Irish Rover” and “William Bloat”. Filk has plenty of comic songs, starting with the immortal and infamous “Banned From Argo” by Leslie Fish, and Tom Smith’s “Seven Drunken Nights in Space”.
A quite serious filk ballad is Gordon Dickson’s “Jacques Chretien”, which comes right out of one of his Dorsai stories–and yes, it’s been recorded.
There’s the “Ballad of Mary Read,” by Peter S. Beagle (I think – at least I’ve got a filk tape where he performs it). Which is based (more or less) on a true story. I can’t seem to find the words online, but I recall it begins:
Come all ye filibusterers and roving buccaneers
Ye rapparees and picaroons and wayward privateers
Ye gentlemen of fortune, roaring captains one and all
Come hear the tale of Mary Read and Dancing Jack Duvall
CHORUS:
And it’s a glass for every prize, and two for every dirty deed
And three more for the soul of wicked loving Mary Read
(In fact, I remember all the lyrics, I’ve done the song in SF-con bardic circles many times – but in light of board policy and Beagle’s ongoing copyright troubles, I will forbear to post any more. 
)
The Tain by The Decemberists is supposedly based on the Irish story Táin Bó Cúailnge. I say supposedly because the lyrics of the song are more like an artistic interpretation of the original story than a faithful retelling of it. The song itself is a medley which repeatedly changes tempos and styles and includes everything from metal riffs to circus music.
Brain Glutton, that’s one of the great things about Mary Read, though - there’s just enough historical evidence to prove she lived, and was a pirate - but the details are so sketchy, and poorly documented, the artist can do most anything with her life, if they so wished. For that matter, there’s reason to question just how accurate the records of her death in jail might be.
You say butchered, I say deftly edited. Our mileage varies, I suppose. 
The Song of Roland is a medieval ballad based on a real event, the Battle of Roncevaux Pass. (Based very loosely – the poet turns the Basques into Moors, in accordance with the Crusading spirit of the time in which he wrote.)
Corn on the cob but Three Wooden Crosses by Randy Travis fits the bill I reckon.
Lily of the West is another, there are a variety of versions by amongst others, The Chieftains and Bob Dylan. Lakes of Pontchartrain and On The Banks of The Old Pontchartrain probably count too. 
Three Fishers, by Stan Rogers – not based on any real event, AFAIK, but definitely a ballad.
The Witch of the Westmorelands, by Archie Fisher (but memorably covered by Stan Rogers).
…and bruised orange…aka chain of sorrow
I would also add…Stella Blue by the grateful dead and may others if i didn’t have to be at get up at 2:30 am for work…
peace my friends…
all fictional I think-
The Killing of Georgie by Rod Stewart
The Alan Parsons Project- Tales of Mystery and Imagination by Edgar Allan Poe
Nick Cave- Where the Wild Roses Grow, with Kylie Minogue
also Cave- Henry Lee, with PJ Harvey