Game with really good story

DooM

+1 Grim Fandango
+1 Deus Ex (the original)
+1 Knights of the Old Republic (the original -- haven't played KotOR 2)
+1 Halo: Combat Evolved (the original -- I really only ever played this on PC and never extensively played the sequels)
+1 Full Throttle (imho, the best game ending ever -- the ending won't blow your mind, it's very simple, but it's perfect)
-1 Indigo Prophecy/Fahrenheit (I love the game, but story-wise, it completely falls apart at the end)

The Bard's Tale

Great!

Shdows of the colossus

I just recently finished Alan Wake and have to say that it has a very cool story

Anchorhead has an amazing story and setting, based on the work of H.P. Lovecraft. Best of all it's free!

Tetris. Some people can't even notice that there is a storyline, but if you do - you'll witness one of the most amazing and epic stories of all times.

Alan Wake, still my favorite game of all time to this day.

try syberia bundle, its pretty good game with a nice plot

Well, usually old games come in mind when talkin bout a good story. But here we go: Deus Ex series, Mass Effect series, Fallout series, Assassin's Creed series, The witcher series (not excelent but good enough), Fahrenheit ( Indigo Prophecy ) heard it has an awesome story, Neverwinter Nights more or less, Bioshock, Dead Space (this is arguable but I like it), The Suffering series, FEAR series, Plancescape Torment, The Legend of Zelda: Ocarina of Time (wish I could play this one :D).
You could also try Half Life series (one of my fav but I didn't find the story excelent but is a good story), Halo maybe (but no Steam), Alan Wake (I kinda like it, no matter what).

to the moon. one of the best story out there

AquaNox 1 and 2.
These two engaged me in a way no game has done in a long time, and I played several listed here.
Keep in mind it's a strong story based game, so if it doesn't catch your attention in the first 15 minutes, you're screwed, 'cause the entire game will be like that.

The Void

Adventure games. All of them. I.e. Monkey Island, Sam + Max, Heavy Rain, etc. Some of them are easy to find :D

Mass Effect is Epic, You will want buy the full trilogy.

So, here's a game you will probably never hear mentioned. Normally.

Shadow of Memories.

PC Adventure game. Rather obscure, I've rarely heard anyone else mention it. A little old, so not the greatest graphics, but one of the most memorable stories I can recall. I played five or six years ago, and it's still fresh in my mind today, even though I haven't played it since. (No longer own it. D:)

It's a really fascinating game involving going back in time to prevent your own death, and dealing with several otherworldly situations along the way. Sometimes, this involved going /way/ back. Overall, it's done exceptionally well, and has several endings depending on your actions. I /highly/ recommend giving it a run through.

Grand theft auto series. these games have a lot of story. I'm serious. Dunno why, but it makes me want to play it (GTA4) and since I've bought it (Summer Sale) i've played 12h and have not even 30% of story completed (based on stats).

And I agree with Danps, Mass Effect Series have one of the best stories ever, Since I've played Mass Effect 2, I've bought whole trilogy, and it's outstanding.

Professor Layton: and the Unwound Future

And cry...

The Walking Dead. There's only 2 episodes out of 5 out now, but it's an awesome adventure game so far.

secret magic crystals?

L.A. Noire

Pretty much everything that I wanted to recommend was already mentioned, except for Binary Domain.

Half Life series

my favourite story games are:
The Walking Dead (omg it was so freakin awesome, but short)
Deus Ex HR (if you read all the books, mails and play stealth and even do missions where you have noone who gave you the mission, and the story is ca 40 hours)
Portal 2 (Epic, but short...)

Am I the only one who enjoyed arma 2 single player?