Ive been thinking about trying out a Strategy game for the first time. The kind of game where you lead different troops over a map, trying to claim territories. Ive never had any interest to play any of those games since it felt a bit to strategic for my taste, but ive realized now that it might be really fun to try one out. Can anyone recommend me a good War-game that can be handled by a newbie? Ive been looking for a fun WWII strategy-game but i haven't decided to get one yet, since most seems overly complicated.

If you're looking for something connected to real history i'd reccomend you the Age of Empires series for starters.
The first game is quite old but is easy to understarnd and has a very accessible learning curve.
I don't remember any WWII strategy games at the moment, maybe some other user has some titles for you :)

Oh, i think you got it all backwards. I want to play a "Strategy game" not a "Real-time Strategy". Turn based all the way. :)

Hearts of Iron 2 if you want to conquer territories in WW2 style. It's a great blend between real-time and turn-based thinking, and it's also what most would consider a hardcore strategy game.
You chose your country from a huge list, form your government (with some historical restrictions), chose your research, form *trading* alliances, and enter war.
Some info:
http://en.wikipedia.org/wiki/Hearts_of_Iron_II
http://www.paradoxplaza.com/index.php?option=com_content&task=view&id=58&Itemid=144

Whoops :) Sorry, my bad.
Unfortunately, turn based games are not my type of thing, i'd better step out and let someone else come to your aid :)

Hearts of Iron is hard. I would recommend Europa Universalis III. Very good strategy.

I'd heartily recommend Civilization 4, although not WWII specifically, it's fun, and can be picked up cheaply. (I'd recommend getting the complete pack, with the add-ons.).

From our catalogue try this:
Jagged Alliance series
MAX
Fallout Tactics
Also look for X-Com series and Heroes of Might and Magic

Bad example, as the strategy aspect is almost entirely lacking. Heck, the single-player campaign being as constrained as it is, even lacks the tactical aspect, making the game more of a puzzle game than anything. It has some sweet turn-based tactics gameplay going on in multiplayer. In short: I really like the game, but "strategy" it is not.
Anyhow, I really liked Age of Wonders. Could give that a shot.

If you don't mind going for a sci-fi turn based game you could try Sword of the Stars its a very streamlined empire building game that lets you spend most your time doing the fun things whithout having to spend ages deciding exactly what to build on each planet and fiddling with taxes. Its got some very interesting races each with their own form of FTL and the tech tree is randomly generated so you dont have to spend hours plotting the optimum way to tech.
It currently has two expansions out giving the game 5 different races i think and adding lots of new ship parts. You can also play it online.

Depends entirely on how you define strategy games :) Today strategy games are supposed to have armies and Incubation has none, but you definitely need a strategy to get through the levels. Do you want to rush through? Do you send a weaker unit to the front to get him to level up for the next mission? Do you take a detour to get more points? Do you take an extra mission to get reinforcements? Do you sacrifice a unit so you can get a flamethrower for another one? Do you risk loosing a unit by using only melee attacks so that you can save your ammunition for a later attack?
There's plenty of strategy in there, even if it doesn't match the typical like-CnC-but-taking-turns boilerplate.

Galactic Civilizations II is a great turn-based strategy game. And it comes from Stardock so it is DRM free. It's much better with its latest expansion installed, but is very good even without it. Great forums too, with tons of good advice and searchable tips. The very good random map/player type generator is a big plus too.
Heroes of Might and Magic 1 and 2 are really excellent too. Fun and full of character. Both are extremely replayable, because they have that holy of holies, a random map generator. And you can adjust pretty much everything you're likely to think of when the game rolls you a new map. Learning a game really well takes time and effort, so having a RMG is really a big plus. It makes your time investment pay off for a long time. You don't want to burn through the maps that came with a game and then be finished with the game, or forced to deal with crummy or hacked ones you download from somewhere on the net.
If you want to try something more on the tactical side but which still has some strategy in it, you can't beat X-COM: UFO Defense. The best tactical level turn-based single player battle engine I've ever played by far, even though it's ancient. It's just really hard, and rare, to get things perfect. The first X-Com does.

My fav. space strategy is Master of Orion 2.
So much fun, so many things one can do.
One time I played Zerg-like race. Even the biggest projects took me few turns to make. My science was weak but what i could not beat with quality i used quantity. so I send waves of ships after ships on my enemy. they die quickly and painfully but they did their job.
and monies were no problem. I simply buy tech from allied nations, sometimes even whole planets.
great game. graphic sux but because of its simplicity it is not a big deal.

Turn based but not overly complicated? If you can find any of them (and occasionally they DO pop up in online store bargain bins) any of the Panzer General series would probably be perfect for you. I would suggest maybe trying Steel Panthers : World at War. It certainly isn't pretty, but it's a very well put together game, and the game is freeware...there is a purchasable version of you want the megacampaigns, but you don't need those. Also still a very active community building new scenarios and campaigns. You can check it out on the Matrix Games site HERE.