God of War. The first one.

"ROOOOAAARRR I'M GONNA MAKE A DEAL WITH THE GOD OF WAR"
"Uh, okay, sure, but you're gonna become my bloodthirsty killing puppet, is that alright?"
"YEAAHHHH FOR THE GLOOORRYYYY"
"Fine, have it your way"
"WHAT HOW DARE YOU MAKE ME UPHOLD MY END OF THE DEAL! AREEEEEEEEEES"

Any game that covers back story with amnesia. Any game that concludes with the main character(s) waking up (SMB2). Any game featuring the same clichés you see in all sorts of writing.

I haven't played Gears of War 2 (for loathe of the first one), but I hear its story is of the shallow variety and mercilessly tacked on. I have no problem with that. People don't necessarily play an FPS for its story. I do have a problem with Cliffy B acclaiming the story, making it out to be the selling point it's not.

I can't name a /worst/ story. Bad Dudes is renowned for it, so I'll say that.

Although I have never played the game, I cannot imagine that MGS4 has the worst storyline in gaming history. If you are being serious can you explain why it is so?

Mario.

Plumbers and mushrooms and turtles that kill you? WTF?

Aside from Sonic...

Star Fox Command. Why? 3 words to describe why: Furry Soap Opera.

Also I have yet to beat it but Final Fantasy X is also a stinker.

MGS 2, Chrono Cross, Persona 3, Tales of Legendia, Jeanne d`Arc, Legend of Legaia, Final Fantasy 7, Final Fight Streetwise.
If I had to chose only one, it would be Chrono Cross.

ffx is an absolute master piece.

for all its phenomenol combat, ninja gaiden (sigma was the only one i played) has a horrible story line.  everyone is either a ninja, a soldier who is a ninja, or a monster.  then to top it all off you could tell the only plot twist about ten minutes into the game.

I somewhat agree with KylieDog too, so it's a tie between God of War and MGS4 for me.

UT3 and their lousy "respawner technology" =/