There has been some obvious recasting in Game of Thrones for characters like Gregor Clegane and Daario Naharis. It also seems to be quite well known that Myrcella Baratheon was recast.
What characters in the show have been recast?
Conan Stevens season 1. Ian Whyte season 2. Hafþór Júlíus Björnsson starting season 3.
Aimee Richardson on seasons 1 and 2. Nell Tiger Free season 5.
Callum Wharry season 1. Dean Charles Chapman season 4. (Fun Fact: Before Chapman was Tommen, he had already appeared as Martyn Lannister in season 3.)
Ed Skrein season 3. Michiel Huisman starting season 4.
David Michael Scott season 1. Richard Dormer starting season 3.
Struan Rodger season 4. Max von Sydow season 6.
Octavia Selena Alexandru season 4. Kae Alexander season 6.
Richard Brake season 5. Vladimir Furdik season 6. Furdik is also the one we see in human form.
Freddie Stroma season 6. Tom Hopper season 7.
Tom Brooke season 3. Daniel Tuite Season 6.
Steven Blount Season 1. John Stahl starting season 2.
Sarah MacKeever season 2 (not credited). Tara Fitzgerald starting season season 3.
From Season 5 onward, Ghost was played by Quigly the real life wolf. Rescued and trained by trainer Andrew Simpson from Instinct Animals for Film.
My answer is largely sourced from what I've seen myself from watching the show and this wikia post. Though the order will largely follow the wikia post so I don't end up forgetting someone.
Originally played by Conan Stevens in Season 1 he was recast to Ian Whyte in Season 2 and finally to Hafþór Júlíus Björnsson for Seasons 4 to 7 (and I believe 8).
For a bit of trivia here Ian Whyte is credited as playing White Walker #1 in the prologue to the series.
Was originally played by Ed Skrein in Season 3 but was recast to Michiel Huisman for Seasons 4 to 6 due to a scheduling conflict for Ed.
Played by Callum Wharry for Seasons 1 and 2 but was recast to Dean-Charles Chapman. Bryan Cogman talks about this here but he essentially states that they wanted a more experienced actor.
For a bit of trivia here Dean-Charles originally played Martyn Lannister in Season 3 before that character was killed off.
Was played by Struan Rodger in Season 4 in the finale and was taken over by Max von Sydow for Season 6.
Was originally played by Richard Brake for Seasons 4 and 5 but was recast to Vladimír Furdík for Seasons 6 and 7 (and likely 8). The new actor also played the First Man version of the character.
Was played by David Michael Scott for Season 1 in a minor role but changed to Richard Dormer for Seasons 3, 6 and 7 (also potentially 8).
Played by Aimee Richardson for Seasons 1 and 2 but was recast to Nell Tiger Free for Seasons 5 and 6.
Was played by Edward Dogliani for Seasons 2 and 3 but was recast to Ross O'Hennessy for a brief appearance in Season 5.
Played by Tom Brooke for Season 3 and Daniel Tuite for Season 6.
Was played by Freddie Stroma for Season 6 but recast to Tom Hopper for Season 7 due to a scheduling conflict.
Originally played by the child actor Octavia Alexandru in Season 4 and was recast to Kae Alexander for Season 6.
Played by Steven Blount for Season 1 and John Stahl for Seasons 2 and 3.
As mentioned in @Möoz's answer the pup Ghost was played by a Northern Innuit for Season 1 and then the wolf Quigly from Season 5 and 6 (and hopefully 8).
Andrew Simpson from Instinct for Film is credited as having been involved in the show since Season 5. He is credited for Season 7 Episode 2, "Stormborn", where only Nymeria shows up. Season 6 Episode 5, "The Door", where only Summer shows up.
It is likely that Grey Wind and Shaggydog were also recast after Season 1 but I haven't found anything to confirm this yet.
The above mentioned wikia page lists a few "Placeholder" characters who were essentially extras and then cast into named roles later on. As such the characters weren't really recast but they are worth a quick mention.
This page does mention Beric Dondarrion and Richard Karstark here but I disagree with the wikia here and instead think of these as actual re-castings.
Worth a mention are the characters that were recast from the pilot to the main production.
Played by Tamzin Merchant and then changed to Emilia Clarke.
Played by Jennifer Ehle and then changed to Michelle Fairley.
Played by Ian McNeice and then changed to Roger Allam.
Played by Richard Ridings and then changed to Dermot Keaney.
Played by Jamie Campbell Bower and then changed to Rob Ostlere.
An honourable mention is Grand Maester Pycelle who was originally meant to be played by Roy Dotrice. However, due to health reasons he had to pull out and we got Julian Glover instead for Seasons 1 through 6. Dotrice eventually plays Hallyne, the pyromancer in Season 2.