I looked at resources in English, particularly here. Whilst I expected some bias, it seemed strange that it was not able to identify anything in the Spanish argument that looked like a case to answer.
I next looked at Spanish Wikipedia. I thought that if there was even a weak case then a potentially biased website like this would be able to find it and express it in a pro-Spanish way. But even that said,
Durante la Guerra de Sucesión Española (1701-1714), se firmó un tratado de paz entre Países Bajos, Reino de Gran Bretaña y España llamado tratado de Utrecht 1713. En este tratado se acordaba que a cambio de la paz internacional, España cedería el territorio que entonces ocupaba Gibraltar (más pequeño que el actual) y Menorca al Imperio Británico de acuerdo con el artículo X del tratado de Utrecht. Los posteriores acuerdos fueron confirmados en París y Sevilla. Años más tarde, los españoles trataron de recuperar la colonia sin éxito, ya fuera mediante uso militar o reclamando el territorio por vías pacíficas.
I translate this as
During the War of the Spanish Succession (1701-1714) a peace treaty was agreed between the Low Countries, the Kingdom of Great Britain and Spain, called the Treaty of Utrecht 1713. In this treaty it was agreed that in exchange for international peace, Spain ceded the territory that then encompassed Gibraltar (smaller than at present) and Menorca to the British Empire in accordance with article X of the Treaty of Utrecht. Further accords were confirmed in Paris and Seville. Years later the Spanish tried to recover the colony without success, both by military means and by claiming the territory by peaceful means.
(If anyone can improve/complete my translation, please do)
Nothing here seems to suggest a valid Spanish claim.
In the previous paragraph it says that
Gibraltar es un territorio no autónomo que, por mandato de la Organización de las Naciones Unidas (ONU), debe ser objeto de un proceso de descolonización.
Gibraltar is a non-autonomous territory which, by mandate of the  UN should be subject to a process of decolonization.
This seems to be based on Resolución 1514 (XV) of the UN which refers to
la unidad nacional y la integridad territorial de un país
the national unity and the territorial integrity of a country
But this seems to be a circular argument as they would have to argue that Gibraltar was part of Spain before they argued that this resolution was in their favour. Clearly the UN cannot base its definition of a country on the boundaries at some particular point in history chosen by an interested party?
So, please, what is the basis for Spain's territorial claim?