When the Spanish arrived in the Caribbean islands, the natives used to cook their meat in two ways: either directly over fire, or they would create a frame of wood and slow roast it over indirect heat and smoke.
Source: Wikipedia
The frame that was used to suspend the meat was translated by the Spaniards to barbacoa. The original Arawak term, barbicu, referred to the framework of wood, which was also used to store food above ground.
The word found its way from Spanish to Portuguese to French to English. It was first used in English in 1661 in Edmund Hickeringill’s Jamaica Viewed: “Some are slain, And their flesh forthwith Barbacu’d and eat”. It was initially used as a verb rather than a noun, and the noun usage evolved later in the century.
The word has also had several spellings, including barbeque, barbecque and barbecue over the years.