What's perhaps even more amazing is that, barring three essential cameos from the TV show (Jeor Mormont, Queen Cersei and Varys), fans won't recognize a single soul in the cast of the game. But the protagonists' stories of loss, hardship, sacrifice, and betrayal are right at home in the world of Westeros.
GoT takes place before and during the events of the first book, and follows two characters whose futures are as entwined as their pasts. Firstly there's Mors Westford, a grizzled veteran of the Night's Watch, an ancient order of sworn brothers ("Crows") tasked with defending the realm from the horrors beyond an enormous, magic wall. Mors is a skinchanger or "warg", which means he can transfer his consciousness to the body of his dog and control it, a concept familiar to book fans.
The second protagonist is Ser Alester Sarwyck, a former knight who fled to another continent after the troubling events of the current king's rebellion a decade and a half before the game. There he became a red priest, a worshiper of R'hllor, the Lord of Light and manipulator of fire. Alester's not chucking fireballs around like a wizard, but his affinity with flames allows him to manipulate it in subtle ways that come in handy during combat.
Alester returns to Westeros upon learning of the death of his father, only to find that Cersei has ordered his sister to marry their bastard half-brother so he, having gained the queen's favor, can rule over the Sarwyck family lands.
Now that's a tale that fits in well in this universe.