The name Gibraltar comes from the Arabic Jabal al Tariq, which means "Tariq's mountain" (for Tariq ibn-Ziyad). Earlier it was Calpe, one of the Columns of Hercules. The territory was ceded to Great Britain by Spain in the 1713 Treaty of Utrecht as part of the settlement of the War of the Spanish Succession. In that treaty, Spain ceded Great Britain "the full and entire propriety of the town and castle of Gibraltar, together with the port, fortifications, and forts thereunto belonging ... for ever, without any exception or impediment whatsoever."

Nonetheless, the treaty stipulates that no overland trade between Gibraltar and Spain is to take place, except for emergency provisions in the case that Gibraltar is unable to be resupplied by sea. Another condition of the cession is that "no leave shall be given under any pretence whatsoever, either to Jews or Moors, to reside or have their dwellings in the said town of Gibraltar." If Britain decides to sell Gibraltar, Spain is guaranteed first purchasing rights.

In a 1967 referendum, Gibraltarians ignored Spanish pressure and voted overwhelmingly by 12 138 to 44, to remain under British sovereignty. Under the 1969 Constitution, Gibraltar attained full internal self-government, with an elected House of Assembly. The preamble to the Constitution stated that "Her Majesty's Government will never enter into arrangements under which the people of Gibraltar would pass under the sovereignty of another state against their freely and democratically expressed wishes."

Major Robert (later Sir Robert) Peliza of the Integration With Britain Party (IWBP) was elected Chief Minister in 1969, although Joshua (later Sir Joshua) Hassan of the Association for the Advancement of Civil Rights (AACR) was returned to power in 1972. In 1976, the IWBP broke up after the British Foreign Office Minister Roy Hattersley ruled out integration with the UK, and was succeeded by the Democratic Party of British Gibraltar.

In response, Spain closed the border with Gibraltar in 1969, and severed all communication links. This remained unchanged after the death of General Franco in 1975. The border was not fully reopened until 1985. Under the 1985 Brussels Agreement, Britain agreed to enter into discussions with Spain over Gibraltar, including sovereignty.

In 1987, a proposal for joint control of Gibraltar's airport with Spain led to widespread opposition locally. Chief Minister Sir Joshua Hassan resigned at the end of that year, to be succeeded by Adolfo Canepa.

In 1988 Gibraltar Socialist Labour Party (GSLP) leader Joe Bossano was elected as Chief Minister, and firmly ruled out any discussions with Spain over sovereignty. In the 1996 election, Bossano was replaced by Peter Caruana, of the Gibraltar Social Democrats (GSD), who while favouring dialogue with Spain, also ruled out any deals on sovereignty.

In 1988, there was controversy when three members of the Irish Republican Army (IRA) were shot dead by the SAS, after they were suspected of planning to bomb a military parade, although a car bomb was later discovered in Spain. In 1991, the British Army effectively withdrew from Gibraltar, leaving only the locally recruited Royal Gibraltar Regiment, although the Royal Air Force and Royal Navy remain.

Spain has made various proposals involving the sovereignty of Gibraltar, which have been rejected by all parties in the Gibraltar House of Assembly. These have involved either joint sovereignty over Gibraltar with the UK, in which the Rock would become a condominium, or full sovereignty, under which it would become an autonomous region , similar to Catalonia or the Basque Country. In 1997, the Spanish Foreign Minister, Abel Matutes made a proposal in which Gibraltar would be under joint sovereignty for fifty years, before being fully incorporated into Spain, but the British government rejected the idea.

In 2001, the British Government announced plans to reach a final agreement with Spain over the future of Gibraltar, which would involve shared sovereignty, but this was decisively rejected in November 2002 when over 98% of the electorate voted against joint sovereignty between the UK and Spain.