The story opens in Hell, with the Devil having just been visited by an angel messenger who told him God was dead (no, it wasn't Nietzsche). The Devil did not believe the news, and ripped a handful of feathers from the angel's wings. When no retribution in the form of a thunderbolt smites him, he realizes it must be true.
The Devil decides he needs to visit Heaven, and find out what exactly has happened. I remember he decides he'll need to pack a lunch for the trip (the story has a semi-serious, semi-comedic tone). The lunch is rather diabolical in nature - I distinctly remember the Devil packing a flask of "Raped Virgin's Tears" to drink should he get thirsty on the way.
When the Devil arrives at the pearly gates, he is confronted by Peter. Naturally, the arch-angel assumes the Devil has come to gloat and/or attack. The Devil does his best to assure St. Peter that he is only there to find out what happened. I forget the details, but God has died and now it appears that Heaven will falter and come to an end without God's power.
The Devil proposes a deal with Peter, offering to let them use a portion of Hell to relocate Heaven. I believe his rationale is that he feel he owes it to his old rival (i.e. God). Or something like that.
I believe the story ends with Heaven being moved to the upper reaches of Hell, where it continues to function and maintains the balance of things, or something like that.
It sticks in my mind this one was in a sci-fi magazine of some sort, and was probably written in the mid-80s or thereabouts. I know for sure that is when I read it.