Originally Setebos was a god of the Patagonians. Patagonia was discovered by Magellan at the southern tip of South America. A fellow voyager, Antoniao Pigafetta, described the discovery in Relations of the First Round-the-world Trip (1536), which was later translated into English and republished in 1555 in Richard Eden's Decades of the New World. The journal describes how the fleet landed to make repairs and sighted a giant on the beach. Magellan named this first giant "Big Foot" (Patagon), and named the surrounding lands Patagonia. The sailors of Magellan's fleet eventually kidnapped two Patagonians, hoping to take them back to Europe and make money from the display of the giants (they died during the course of the voyage). There are those who believe that the Patagonian who was renamed Paul was the basis for Shakespeare's Caliban, who was to be kidnapped by Trinculo for display in England.
Setebos is explicitly mentioned in Pigafetta's journal, which was also carried forth into Eden's book, and picked up by Shakespeare.
"When one of those people die, ten or twelve demons all painted appear to them and dance very joyfully about the corpse. They notice that one of those demons is much taller than the others, and he cries out and rejoices more. They paint themselves exactly in the same manner as the demon appears to them painted. They call the larger demon Setebos, and the others Cheleulle. That giant also told us by signs that he had seen the demons with two horns on their heads, and long hair which hung to the feet belching forth fire from mouth and buttocks. The captain-general called those people Patagoni (bigfeet). They all clothe themselves in the skins of that animal above mentioned; and they have no houses except those made from the skin of the same animal, and they wander hither and thither with those houses just as the Cingani do. They live on raw flesh and on a sweet root which they call chapae. Each of the two whom we captured ate a basketful of biscuit, and drank one-half pailful of water at a gulp. They also ate rats without skinning them." (Diary of Pigafetta, p.61).
Setebos is mentioned exactly twice in The Tempest (1611), both times by Caliban:
Act I, Scene II - No, pray thee!
I must obey: his art is of such power,
It would control my dam's god, Setebos,
And make a vassal of him.
Act V, Scene I - O Setebos, these be brave spirits indeed!
How fine my master is! I am afraid
He will chastise me.
The Lovecraftian nature of Setebos was established by Robert Browning in Caliban Under Setebos (1864), where he is described as:
’Careth but for Setebos
The many-handed as a cuttle-fish,
While Setebos was not explicitly used by Lovecraft, he did use the Cuttlefish term to describe a sculpture of Cthulhu in The Call of Cthulhu. The Setebos of Ilium is not from our Earth. Like the Voynix he comes from elsewhere. Caliban has some interesting tidbits to say about Setebos:
Thinketh, Himself, that the posties brought wormholes, Setebos brought the worms
Prospero made maggots into gods, and Setebos made stone into Prosper’s face, and zeks to place him well.
Thinketh, Himself, Prosper brings crafty Odysseus here, but Setebos makes him wander.