Elder Thing - "This minion is not affected by opponents' cards."
It's quite explicit: "This minion is not affected by opponents cards." That means any cards, so it doesn't get shuffled to the bottom of the deck. It will stay in play.