When the great ice-sheets covered the north, life retreated before them, but some species stayed and endured. Whilst man huddled around fires in his caves, mighty beasts roamed the tundra: the Woolly Mammoth, the Woolly Rhinoceros…and the Woolly Wyvern.
The PCs are sent with a diplomat to another country to protect him and do his bidding. There may be some espionage, rescuing, downright bullying, etc. Could make a nice medieval, special operations background.