The song was written by vocalistJoey Tempest in 1985, and was in fact the last song written for the album. The video for "Cherokee" was filmed in September 1987, in Almería, Spain. It was filmed a half mile from where Sergio Leone shot the famous Clint Eastwoodspaghetti westernA Fistful of Dollars. When filming the scene where the horses run through the valley, someone accidentally set some brush near the set on fire. The entire video crew, including band members, had to fight the fire by quickly digging a trench around the fire to stop it spreading. Historically, the video is very inaccurate. It showed the Cherokee as plains Indians, living in teepees on the desert. The Cherokee originally lived in the wooded, southern Appalachian Mountains. They were forcibly moved to the wooded, rolling hills of eastern Oklahoma. The Cherokee never used teepees.