“Bowie Knife” by Frankie Lane.
“Famous Flower of Serving Man” and “Willie’s Lady” - Martin Carthy - plus tons of other ballads he’s recorded
“Tam Lin” and “Matty Groves” - Fairport Convention
“Willy o’ Winsbury” - Pentangle
In a different vein, “Henry” and “Dirty Business” - New Riders of the Purple Sage
“Me toos” for “Hurricane,” “Long Black Veil,” “1952 Vincent Black Lightning.”
“Scenes From An Italian Restaurant” - Billy Joel
Let us also shed a tear for One Tin Soldier by Coven, and Cher’s Gypsies, Tramps, and Thieves. 
Another good ‘un: Tweeter and the Monkey Man, by The Traveling Wilburys.
A story and a fairly accurate historical account -
Al Stewart - Roads to Moscow
From the perspective of an unlucky Russian soldier pining for his home it tells the story of the WWII German army racing through Russia with ease on its way to Moscow. Repeating Napoleon’s mistake the Germans are cut off from the rear by the harsh Russian winter and then ambushed repeatedly during retreat.
In the end the Russian army is on its way to Berlin and has little trouble dealing with the “old men and children” that are the last line of defense of that city.
But for his years of service fighting the Germans the unlucky soldier is sent off to one of Stalin’s Siberian camps because he was briefly a prisoner of the German army.
The lyrics read as a poem are fantastic while Steart’s voice and musical arrangement create a hypnotic an compelling experience.
Yeah, Tom Waits is the king. Not originally by Waits, so maybe it doesn’t count, but I LOVE his “Big Joe and Phantom 309.”
Joe
“Country Death Song” - The Violent Femmes
Ooh, wish I’d mentioned this one myself. Incredible song. Stewart’s gentle, almost dispassionate vocal delivery makes it even more chilling.
Uneasy Rider - Charlie Daniels, wins my vote for - funniest. song. ever.
Other songs that have stories:
Of course, the ‘murder ballads’ mentioned in another ongoing CS thread.
“Dark Lady” by Cher (hate the song, but it is nevertheless a story song.)
“One Tin Soldier” (Ugh, ditto)
“Space Oddity” by David Bowie
Short and sweet Paul Kelly To Her Door
The fantastical The Strange Case Of Frank Cash And The Morning Paper by T-Bone Burnett, one of the cleverest uses of the pop song ever. About a guy who finds that his daily paper lists next weeks football scores. Shades of Early Edition. Pretty funny too.
And what about Eminen’s Stan.
Add:
“Dress Rehearsal Rag” and “Joan of Arc” - Leonard Cohen
David Bowie - “Ground Control To Major Tom”
Kylie Minogue & Nick Cave - *Where The Wild Roses Grow *
Randy Travis - Three Wooden Crosses
Tom Petty & The Heartbreakers - Into The Great Wide Open
Harry Chapin’s ‘30,000 lbs of Bananas’
Warren Zevon’s “Hit Somebody” or “Roland the Headless Thompson Gunner”
This one’s my favorite.
You never even called me by my name
Featuring the immortal line: I was drunk the day my mom got outta prison
“The Battle of New Orleans” by Johnny Horton.
I so love that song. We learned it in school when I was nine.
Two all-time favourites:
House of the Rising Sun (the Animals version).
Roland the Headless Thompson Gunner (Warren Zevon).