Not so long ago, the compound reverberated to the sound of incoming rocket fire from Iraqi insurgents, the Mahdi Army Shia militia, as they fought British forces based at the palace.
British soldiers withdrew from the palace compound in September 2007. Now, the building itself is deserted, and I have to wait for an Iraqi police colonel to turn up with the key.
Built by a Basra oil baron in the 1980s, the palace was requisitioned by Saddam Hussein, although it is not clear if the late dictator ever stayed there.
I had not seen it since April 2003, when a British flag flew triumphantly over the entrance, and British troops - rejoicing in the rapid success of the invasion - explored Saddam's palaces, wide-eyed with wonder at their opulence, and the gold taps in the many bathrooms.
Water, electricity, antiquities
That was in the early days, when the people of Basra offered a warm welcome to their British "liberators". It was before the long years of violence began, and back then the palace itself had been spared the worst effects of battle.
In his mind's eye, John Curtis, keeper of the Middle East department at the British Museum, can already see the site transformed into a museum for Basra's many ancient treasures. Before I left for Basra, I met him in the British Museum's rooms full of Assyrian wall reliefs, and had just enough time to marvel at the exhibition on ancient Babylon, a place not far from today's Basra.
"The front of the palace could have a marvellous fountain and ornamental gardens," he enthuses. He was also the first western expert to see for himself and catalogue the catastrophic effects of looting, battle and ignorance on the archaeological sites of ancient Mesopotamia, now southern Iraq, following the coalition invasion in 2003.
He says he and his Iraqi counterparts at the Baghdad Department for Antiquities, which oversees Iraq's museums, hope the Basra project will come to fruition despite the difficulties that remain.
"They're enthusiastic about the project, and glad we're taking this initiative," he says. "A great deal has been done in Basra in terms of providing water and electricity. But culture is an area which has been largely neglected."
Just a few years ago, the very idea of a new museum in Basra would have been laughable. The focus was on security, and reconstructing the essentials of daily life, such as a working sewage system. Those projects are still not complete, but more than five years on, Basra is indeed a place transformed, with British forces looking to withdraw from the region altogether by the end of July.
The city is much calmer now, with Iraqi forces handling security while the British focus on training. Car bombs, kidnappings and even murders are down from their peak, even if they have not disappeared entirely. And British troops are even back in the wider Basra Palace complex again, while they mentor the Iraq Army in the city.
The origin of the idea of a new Museum for Basra based at the palace came from Maj Gen Barney White-Spunner, Britain's former commanding officer in southern Iraq, and was taken up with enthusiasm by Mr Curtis and the British Museum.
Basra's collection of antiquities have survived somewhat against the odds. The city's old museum was ransacked during the first Gulf War of 1991, and its valuable collection of vases, terracotta and stone figures, bronze weapons, jewellery and cuneiform-inscribed clay tablets, were moved to the capital, where they were locked in a vault. That's how they escaped the 2003 looting.
As I walk inside Basra's silent palace, I am accompanied by Capt Laurence Roche, of 20th Armoured Brigade, who is helping continue the liaison work. He remembers being there in 2006, and the imposing main room overlooking the Shatt al-Arab waterway, being used as a British Army cook-house, with the rooms upstairs becoming dormitories.
"It's eerie to see the palace so empty, but with all the grandeur of the rooms, and the view... it's not too much of a leap of the imagination to see this as a museum. I know we in the British Army are fascinated by our own history and the ancient history here, because this is one of the cradles of civilisation - with so many treasures. Many of us would like to return in future years and see that in its proper setting," he says.
But how do Iraqis feel about the idea? Col Ahmed Abbas Hudea, who let us into the palace, is enthusiastic.
"I would be happy if all of Saddam's palaces were turned into museums for Iraqis to enjoy," he says. "And I hope people would come to visit from across the Arab world, and from Western countries."
In December, Capt Roche had a small glimpse of the kind of treasures the museum could contain one day. He was allowed to film some 200 priceless ancient artefacts, the fruits of a raid by Iraqi security forces on a gang of smugglers who had buried their horde in a Basra back garden. They were destined for private buyers abroad. Capt Roche says it was an Aladdin's cave.
"There were statuettes, just five or six inches high, representing Babylonian kings and Sumerian warriors and princesses. And there was a lamasu - the winged ox that was the symbol of Assyrian strength, and silverware and jewellery. And they had found Babylonian gold, absolutely priceless. It was a spectacular haul."
It is not clear if those artefacts will go into the museum. They are currently being examined by experts in Baghdad, who say Basra is an extraordinary city, with deep-rooted heritage, which deserves a new site for its treasures.
However, they say that their mutual efforts with their British colleagues have been delayed by the need to seek official Iraqi cabinet approval, although they vow to continue to "aspire" to the idea.
So, if the ambitious plans work out, people in southern Iraq should one day be able to enjoy a splendid new setting for their ancient heritage, in a building that symbolises so much of Basra's more recent turbulent history.
Until that day comes, it is still easier for visitors to enjoy many of Iraq's ancient treasures in the British Museum - not least because Basra and Baghdad are not quite back on the tourist trail just yet.