The UN agency that regulates international aviation transport has been based in Montreal from its beginnings in 1947. Its lease expires in 2016, and the agency's governing council had recommended renewing the lease.
But last month, Qatar submitted a proposal to move the office to Doha, offering generous financial incentives to the organization.
News that Qatar had withdrawn its bid came from Foreign Affairs Minister John Baird on Twitter.
"Pleased to confirm Qatar has withdrawn its bid to move ICAO HQ from Montréal," Baird tweeted Friday.
Anthony Philbin, an ICAO spokesman, said the agency received a letter from Qatar's charge d'affaires in Ottawa late Thursday saying it was withdrawing its offer to move the agency. Philbin said the letter gave no reason for the decision.
Paradis told reporters on Parliament Hill Friday that Ottawa's campaign in partnership with Montreal and Quebec lobbied 100 countries to keep ICAO in Montreal.
Paradis was asked what concessions Canada made in the face of Qatar's attractive offer.
"It was just our lobbying efforts that paid off," Paradis said in French, and noted that ICAO had been in Montreal since 1947 and there was a level of expertise built up around it. "That was certainly a very winning argument for us. And we received the support of a number of countries that we lobbied, which meant that Qatar backed down."
Baird paid tribute to that partnership on Twitter Friday morning.
"Would not have been possible without great teamwork between our government, @jflisee and @MapplebaumMTL," Baird said in a second tweet, referring to Quebec International Relations Minister Jean-François Lisée and Montreal Mayor Michael Applebaum, with whom Baird had formed a "Team Montreal" aimed at thwarting Qatar's bid to move the agency.
MPs also overwhelmingly supported a motion in the House of Commons May 2 to back the governments' attempts to keep the headquarters in Montreal.
In a statement issued Friday, ICAO secretary general Raymond Benjamin said the agency is pleased to be staying in Montreal, which "has been our home for many decades."
"While the offer to move us to Doha was extremely generous, ICAO is also very pleased to continue its global mission with the support and co-operation of the Canadian and local governments who have hosted our headquarters for so many years now," Benjamin was quoted as saying.
Qatar's offer to move ICAO would have required the approval of at least 60 per cent of the organization's 191 members. A vote was not expected before September.
Observers warned that losing the United Nations' only office in Canada would cause both political and economic damage. The agency's presence in Montreal brings an estimated $120 million in economic benefits to the city specifically and to Canada's aviation industry generally.
News of Qatar's bid led to speculation that Canada's reputation as a staunch supporter of Israel and its criticism of some UN bodies might work against its attempts to keep the organization's headquarters in Montreal. As well, some pointed to a 2010 dispute with Qatar's Gulf neighbour, the United Arab Emirates, over landing rights in Canada. But Baird said those concerns were misplaced and said he'd enjoyed a "good visit" to Qatar just a month earlier.
"I would characterize our relationship with the Arab world to be excellent," Baird said at a press conference May 3 following a meeting with his "Team Montreal" counterparts.
Prime Minister Stephen Harper also weighed in on the matter, saying he wasn't aware of "any serious complaints" about how Canada hosts the organization.
"Montreal is a sophisticated city that is a hub of the aerospace industry around the world," the prime minister said May 3. "There is absolutely no reasonable case to move the centre out of Montreal."
Also on HuffPost