As is the case for most chansons de geste, it is difficult to establish a precise date for the composition of Gui of Burgundy. Scholars have agreed on the beginning of the thirteenth century, perhaps around 1211, since the manuscript of Tours mentions a marchois – a coin that was not minted before this date. More important, another chanson, written around 1230–34, alludes to the gist of the Gui of Burgundy story, thus situating our text before these dates, in the first quarter of the thirteenth century.

The same uncertainty remains about a possible historical background. Several hypotheses have been proposed, but none is verifiable. One suggests that the Gui of Burgundy legend might have to do with the powerful family of Burgundy that fought several crusades against the Muslims during the eleventh and twelfth centuries. One Gui of Burgundy did exist. He was the great-grandson of Richard I of Normandy. He became pope Calixtus II and was regent for his nephew, the future king of Castile and León in Spain. Interesting as it may be, such a reference is vague and inconclusive. All we can say, at this time, is that the chanson reflects the skirmishes against the Islamic enemy in Spain illustrated by many epic texts and especially those involving Charlemagne and his peers.

When the story begins, Charlemagne has been campaigning in Spain for twenty-six years. Spurred by a mocking remark from one of his twelve peers, Richard of Normandy, the emperor decides to stay even longer in order to seize five cities that escaped his authority. Although an angel appears ordering him to go directly to the city of Luserne, Charles persists in besieging the other four, each for a year, without success. On the advice of Naimes, one of his peers and his main counselor, he finally goes to Luserne, which he besieges in vain for seven years.

At the same time in France, the sons of the twelve peers, frustrated by the emperor's excessive absence, gather in Paris to designate a substitute king who would maintain order in the kingdom while Charles is in Spain. Bertrand, Duke Naimes's son, proposes offering the crown to the young Gui of Burgundy.