It was just another false start in three decades of efforts by Trump to crystallize ties with a country that has long captivated him.
His Miss Universe beauty contest was taking place in Russia's capital and he thought it would seal a connection with its president, Vladimir Putin.
"Do you think Putin will be going to The Miss Universe Pageant in November in Moscow -- if so, will he become my new best friend?" the now US-president elect tweeted.
The meeting never took place, though Putin sent a close aide with a gift for the American.
It was just another false start in three decades of efforts by Trump to crystallize ties with a country that has long captivated him -- for its real estate development potential, but also for its steely, no-nonsense leaders.
Trump wrote in his book, "The Art of the Deal," that his attraction to the then-Soviet Union began in 1986, when a lunch with Soviet ambassador Yuri Dubinin turned into an investment opportunity.
"Dubinin's daughter, it turned out, had read about Trump Tower and knew all about it," Trump recalled.
"One thing led to another and now I'm talking about building a large luxury hotel, across the street from the Kremlin."
He traveled with his then-wife Ivana to view potential sites in Moscow the following year.
"It was an extraordinary experience," he wrote. "I was impressed with the ambition of the Soviet officials to make a deal."
Nothing came of it, and over the next decade Trump was bogged down in the bankruptcies of his Atlantic City casinos. But by 1997, he was back on the Russia file, bonding with rising political star General Alexander Lebed.
The two met at Trump Tower, where, according to a New Yorker article, Lebed lauded Trump's Moscow hotel plans as "a litmus testing paper" for American capital flowing to Russia.
Basking in the praise, Trump gave Lebed, a former boxer, a copy of his book. After the meeting, the New York tycoon said what he really liked about the Russian.
"Does he look as tough and cold as you've ever seen? This is not like your average real-estate guy who's rough and mean," Trump said. "This guy's beyond that. You see it in the eyes."
Trump's trip to Moscow that year again came up dry, but he was smitten with the country and its hard-nosed leaders more than ever. Entertaining his first White House run in 2000, he wrote in a new book of his fascination with Russian power.
"What I don't understand is why American policymakers are always so timid in dealing with Russia on issues that directly involve our own survival," he said, pointing to his experience of Lebed, "a really tough guy" who he predicted would one day lead Russia.
Trump backed out of the 2000 race, and Lebed died in 2002 in a helicopter crash. By then, ex-KGB officer Putin was the country's president, and Trump's eyes turned to the vast sums of money newly rich Russians were moving out of the country.
In 2005, he went into business with New York developer Bayrock Group, led by two immigrants from the former Soviet Union.
They signed a deal to develop a Trump Tower in the Russian capital that went nowhere. Meanwhile, they built the 46-floor Trump Soho luxury apartment tower in New York City, and other Trump-brand developments in Florida.
The primary financing source and the marketing target, were both Russian money, including an Iceland-registered investment firm identified in later lawsuits as "in favor" with Putin.
Trump was not implicated in the lawsuits, but in a deposition he bared his view of the situation.
"Russia is one of the hottest places in the world for investment. We will be in Moscow at some point," he said.
Again eyeing the White House in 2007, Trump began singing Putin's praises.
"Look at Putin -- what he's doing with Russia," he told CNN.
"Whether you like him or don't like him -- he's doing a great job in rebuilding the image of Russia and also rebuilding Russia, period. Forget about image."
After Trump sold the Palm Beach, Florida estate Maison de L'Amitie to Russian billionaire Dmitry Rybolovlev for a record $95 million in 2008, his name became bigger inside Russia, and he entertained journalists from Moscow.
"I really like Vladimir Putin. I respect him. He does his work well. Much better than our Bush," Trump told them.
By 2011, Trump began planning a serious White House challenge. For him, comparing President Barack Obama to Putin was a way of standing out.
In his new political tract, "Time to Get Tough: Making America #1 Again," he praised Putin for "his intelligence and no-nonsense way."
"I respect Putin and the Russians, but cannot believe our leader allows them to get away with so much," he wrote. "Hats off to the Russians."
By 2013, the year of the Miss Universe contest in Moscow, Trump had another deal to build a Trump Tower by the Kremlin.
It didn't happen, but his praise of Putin stepped up. He lauded Putin's op-ed in The New York Times telling Washington how to make peace in Syria.
"He is lecturing to our President. Never has our Country looked so weak," Trump tweeted.
His pro-Russia views under increasing scrutiny in 2015 as he opened his campaign, Trump made waves for casually dismissing longstanding suspicions that Putin's regime condoned the murder of critical journalists.
"It's never been proven that he's killed anybody," Trump told ABC.
Having conquered the White House in a victory loudly cheered in Moscow, he continues to brush off reports of brutality and repression by Putin's Kremlin.