“Beep Beep” by the Playmates. (I always thought it was called “His Horn Went Beep, Beep, Beep.”)
Oh Life (There Must Be More) by Alan Parsons
30KFT by Assemblage 23
(these are also my go-to songs for “depressing songs” threads, but they do fit as story songs too. 
)
Oh the Irish are great for the stories. Kilkelly, IrelandIt’s a true story and depressing as hell.
Four Green Fields
Fields of Athenry
Johnny Horton was good for it too. Sink the Bismarck
Battle of New Orleans
And don’t forget Gene Pitney. The Man Who Shot Liberty Valance
“John Barleycorn Must Die” (trad. but Traffic’s version is great)
“Back by Fall” - Wendy Waldman
“Our Town” - Iris DeMent
“Hippie Boy” - Flying Burrito Brothers 
Lots of great recommendations so far, but can’t believe that Tom T. Hall (The Storyteller) hasn’t been mentioned.
Ballad of 40 dollars is good one.
And if you want to laugh and get some good advice at the same time, try Tim Wilson’s “100 Things Every Man Should Know”.
“Old Admirals” by Al Stewart is a biography; the narrator goes from his first voyage at age 15 to his retirement.
“Saturday Night Fish Fry” by Louis Jordan.
Jim Croce’s “Bad Bad Leroy Brown” or “You Don’t Mess Around with Jim.”
Oh, and I just have to add Alan Jackson “The Talkin’ Song Repair Blues”
Another vote for Stan Rogers’ oeuvre. Those songs already mentioned, but also:
For other artists work:
I’d also second the vote for Dawson’s Christian. (I believe this is being sung by Duane Elms, but I wouldn’t care to wager anything I can’t afford to lose based on that belief.)
I’ll second Cold Missiouri Waters, the version I’m familiar with is the one from the Cry, Cry, Cry album.
Great Big Sea has a number of excellent ones. Right now my current favorite is the title track from their most recent album, Safe Upon the Shore.
More cheerful is The Mary L. McKay, here performed by Schooner Fare.
And general recs for most anything by Harry Chapin.
A couple others I wanted to get in:
Silly Wizard has many, but one of my favorites is Twa Brithers.
Maddie Prior (of Steeleye Span) and June Tabor collaborated on two excellent folk albums, as the duo Silly Sisters. They also have a number of excellent story songs.
Two of them are:
Finally, a compelling story, but deliberately left unfinished is Mercedes Lackey’s Lammas Night, here performed by Alexander James Adams before he transitioned.
“Rime of the Ancient Mariner” - Iron Maiden
In the hotly contested “Story Songs About Cannibalism”, we can only burp in awe at the Buoy’s Timothy.
My apologies if this sort of thing is not to your taste.
Regards,
Shodan
Charlie Daniels Uneasy Rider
Looking Glass Brandy
Eagles Hotel California
Another classic in song form – “Moby Book” by Steve Goodman.
Snoopy vs. the Red Baron is quite a tale.
Steve Earle Copperhead Road
You are joking, right?
I’m going to say “The Night Chicago Died,” cause I’m guessing no one else mentioned it!
Also, “Love Vigilantes” by New Order. A fave of mine.
1952 Vincent Black Lightning
Beeswing
Sidney Wells
Guns are the Tongues
All by Richard Thompson
An Englishman Abroad - Martin Simpson
Hollow Point - Chris Wood
Tam Lyn (Retold) - The Imagined Village
I’ll add some Fountains of Wayne songs to the list:
Red Dragon Tattoo
Action Hero
Sick Day
All Kinds of Time
Someone to Love
Richie and Ruben
A lot of these have probably already been mentioned (I haven’t read through the thread yet), but…
Uneasy Rider (Charlie Daniels)
Guitar Town (Steve Earle)
Old Dogs, Children and Watermelon Wine (Tom T Hall)
Johnny Come Lately (Steve Earle)
Apple Jack (Dolly Parton)
The Marvelous Toy (Chad Mitchell Trio)
Daisy a Day (Jud Strunk)
The One on the Right Is on the Left (Johnny Cash)
Talk to Me, Fiddle (Charlie Daniels)
The Ballad of Ira Hayes (Johnny Cash)
El Paso (Marty Robbins)
One Piece at a Time (Johnny Cash)
Harper Valley PTA (Jeannie C Riley)
Ode to Billy Joe (Bobbie Gentry)
Song of the South (Alabama)
Golden Ring (George Jones and Tammy Wynette)
Sink the Bismarck (Johnny Horton)
The Battle of New Orleans (Johnny Horton)
Snoopy’s Christmas (Royal Guardsmen)
The Golden Vanity (Chad Mitchell Trio)
The Night the Lights Went out in Georgia (Vicki Lawrence)
The Gambler (Kenny Rogers)
Bed of Rose’s (Statler Brothers)
Convoy (C W McCall)
Crispy Critters (C W McCall)
Wolf Creek Pass (C W McCall)