As confirmed in this post, Paradox Development Studio has released the Linux version of Crusader Kings 2. This game is expected to be just the first of many Linux titles coming out of Paradox.
Crusader Kings 2 was released in H1'2012 for Windows and Mac OS X as a grand strategy game set in the middle ages. This title is powered by the "Clausewitz" Game Engine. The expansions to this game and extra downloadable content are now all available via Linux.
More details on this game can be found from the Steam web-site and the YouTube video below.