Fabian Picardo revealed that he has been speaking with Nicola Sturgeon, Scotland's First Minister, about exploring their options as countries that both want to remain within the EU.
Speaking to BBC's Newsnight on Tuesday, Picardo said: "I can imagine a situation where some parts of what is today the member state United Kingdom are stripped out and others remain.”
"That means that we don't have to apply again for access, we simply remain with the access we have today, and those parts that leave are then given a different sort of access, which is negotiated but not necessarily under Article 50."
Gibraltar is heavily reliant on EU membership not least because it allows freedom of movement across its border with Spain.
Fabian Picardo. Photo: AFP
The tiny territory of 33,000 people relies heavily upon workers living in Spain, supplies imported from Spain and its ability to trade to within the European Common Market.
As expected in the referendum on June 23rd, Gibraltar backed remaining part of the EU with a massive 96 percent mandate (19,322) on a turnout of 84 percent.
Likewise all 32 Scottish council areas voted to remain, with a total of 62 percent (1.6 million) on a turnout of 67 percent.
Mr Picardo continued: "The position of the people of Gibraltar is that we've expressed, perhaps even more clearly than the Scots, what our view is going forward, what should happen - that we should continue to have access to the single market of the European Union.
“My obligation is to protect and promote the interests of Gibraltar and to find such partners who may be willing to do the same thing within the United Kingdom."
Sturgeon said talks were in order to build a “common cause” with Gibraltar to maintain links with EU.
She travelled to Brussels on Wednesday to begin negotiations with EU leaders and is expected to push for a second independence referendum for Scotland.
Gibraltar has said that under absolutely no circumstances would it consider a joint sovereignty agreement between UK and Spain.
“There will be no talks, or even talks about talks, about the sovereignty of Gibraltar,” Picardo said in a speech to Gibraltar's parliament just hours after the Brexit vote.
Picardo's comments came in the wake of Spain implying it was closer to bringing Gibraltar under its control.
“The Spanish flag is much closer to the Rock,” said Spain's acting foreign minister, José Manuel García-Margallo on Friday morning in response to Brexit.
David Cameron, who will remain as British Prime Minister until October, sought to reassure Gibraltar that their interests would be protected in Brexit negotiations, but UK Foreign Secretary Philip Hammond admitted that would be difficult.
In an interview with ITV's Robert Peston on Sunday, Mr Hammond warned: “We will be less able to protect Gibraltar's interests, not to defend Gibraltar's territory, of course we can do that, but to protect Gibraltar's interests if we are not in the European Union,” he said.
“Gibraltar depends on thousands and thousands of Spanish workers crossing that border every day and any disruption to that flow will be extremely damaging to the Gibraltar economy.”