Senator Xenophon said Malaysia's opposition had expressed concerns that an election, to be held by the end of April, would not be fair and would not reflect the will of the people.
He and other Australian MPs were to meet opposition leader Anwar Ibrahim, as well as Malaysia's minister in charge of parliamentary affairs, Mohammed Nazri, and members of the group Bersih, the Coalition for Clean and Fair Elections.
"It seems that a member of the Australian parliament is not allowed into Malaysia because I am a supposed security risk," he told Sky News.
Senator Xenophon arrived in Kuala Lumpur on Saturday morning, a day ahead of the other members of his delegation, Liberal Dr Mal Washer, Nationals Senator John Williams and ALP MP Steve Georganas.
Malaysian immigration officials told him there was a technical glitch with his passport, then escorted him to an area of holding cells, although he was not put in a cell.
He was allowed to keep his phone, which enabled him to conduct interviews with Australian media. He also transmitted an image of himself awaiting deportation.
"I was eventually told apologetically by immigration officials that I am on a watchlist, that there are orders from above in terms of security concerns and I have to be deported on the next flight out of here," he said.
Senator Xenophon acknowledged he had been critical of Malaysia's human rights record.
Last year he visited Malaysia as a member of an international fact finding mission, invited by opposition leader Anwar Ibrahim to assess the electoral system.
During the visit he observed a large demonstration calling for electoral reform. TV images show he was close enough to experience the effects of tear gas fired by authorities to disperse protesters.
Senator Xenophon later told parliament there were serious concerns about the integrity of the country's election rolls ahead of the election.
The election is expected to be a close contest between the National Front coalition, which has governed Malaysia since independence from Britain in 1957, and opposition leader Anwar's three-party alliance.
Senator Xenophon's detention prompted a diplomatic flurry.
Foreign Minister Bob Carr said Australian High Commissioner Miles Kupa had made direct contact with Senator Xenophon at the airport and was seeking his release.
Mr Kupa was also urgently pursuing an explanation from Malaysian authorities. As well, Australia's concerns had been raised with Malaysia's Foreign Minister, Minister for Home Affairs and High Commissioner to Australia.
Senator Carr said he had personally sought to contact Malaysia's foreign minister.
"We are seeking a full explanation of this. We think it is sad for a friendly country to deport an Australian member of parliament who was up there for peaceful purposes," he told reporters in Sydney.
Senator Carr noted that Australia didn't send official election observers to other countries unless they were invited.
"He was going there as a member of parliament in a private capacity and we find it disappointing that he is turned away," he said.
No Malaysian officials have explained why Senator Xenophon was detained.
Ibrahim Yaacob, chief of staff to opposition leader Ibrahim, said the deportation was a black mark for Malaysia.
"Where is the fair play, where is the democracy? It's not as if the senator is a terrorist," he told the Associated Press in Kuala Lumpur.
Senator Williams said the visit, planned two months ago, would not proceed but he did not believe a protest by Australia would help.
"They have their reasons why they stopped him at the airport and I'm sure in time these can be talked through," he said.
"It will settle down in a few weeks' time and we'll look at whether we can make a visit then."Senator Xenophon was expected to depart late on Saturday, Kuala Lumpur time, and arrive in Melbourne on Sunday morning.