Game of Thrones Fan art- Having trouble with the background

[Piotr Jasielski]

You might try to separate the layers of character an background, then paint the background normally then play with filters and atmospheric perspective - for example use the blur filter or add a layer of atmosphere in between them. This might be easier than to paint it blurred right away and you will have more control over it.