The population of northern and western Navarre is largely of Basque stock, and the early history of the region is that of the Basques. The pass of Roncesvalles, which leads from France to Navarre, made the region strategically important early in its history. The Basques defended themselves successfully against the Moorish invaders as well as against the Franks; the domination of Charlemagne, who conquered Navarre in 778, was short-lived. In 824 the Basque chieftain Iñigo Aritza was chosen king of Pamplona, which was expanded under his successors and became known as the kingdom of Navarre. It reached its zenith under Sancho III (reigned 1000–1035), who married the heiress of Castile and ruled over nearly all of Christian Spain.

On Sancho's death the Spanish kingdoms were again divided (into Navarre, Aragón, and Castile). The kingdom of Navarre then comprised the present province of Navarre, the Basque Provinces (which were later lost to Castile), and, north of the Pyrenees, the district called Lower Navarre, now a part of France. In 1305, Navarre passed to King Philip IV of France. Navarre stayed with the French crown until the death (1328) of Charles IV, when it passed to Charles's niece, whose son, Charles II (Charles the Bad), played an important part in the Hundred Years War and in the French civil unrest of the time. In 1479, Navarre passed, through marriage, to the counts of Foix and then to the house of Albret. Ferdinand V (Ferdinand the Catholic), after defeating Jean d'Albret, annexed most of Navarre in 1515. The area north of the Pyrenees (Lower Navarre) remained an independent kingdom until it was incorporated (1589) into the French crown when Henry III of Navarre became King Henry IV of France. It was united with Béarn into a French province.

Until the French Revolution the kings of France carried the additional title king of Navarre. Since the rest of Navarre was in Spanish hands, the kings of Spain also carried (until 1833) the title king of Navarre. During that period Navarre enjoyed a special status within the Spanish monarchy; it had its own cortes, taxation system, and separate customs laws. In 1833, Navarre became the chief stronghold of the Carlists but recognized Isabella II as queen in 1839. As a reward for their loyalty in the Spanish Civil War, Franco allowed the Navarrese to maintain their ancient fueros, which were charters handed down by the crown outlining a system of self-government.