Leshchinsky wasn't a soldier.
A reporter for Soviet television, he was dispatched to Afghanistan in 1985, shortly after Mikhail Gorbachev came to power, to cover the final stages of a war in which Moscow was rapidly losing faith.
His last report from Afghanistan shows General Boris Gromov leading the few remaining Soviet troops out of the country on February 15, 1989.
In the now historic images, Gromov is seen strolling toward Leshchinsky across the Friendship Bridge that once separated Afghanistan from the Soviet Union before declaring the nine-year war officially over.
Gromov's teenage son then leaps into his arms, clutching a bouquet of carnations.
It was a carefully orchestrated scene intended to spin the pullout as a dignified exit rather than a retreat following a devastating conflict that claimed the lives of 15,000 Soviet soldiers and an estimated one million Afghans.
Leshchinsky nonetheless recalls February 15, 1989, as a deeply moving day.
"My voice was shaking, and his too," he tells RFE/RL. "When he said he would like to erect a monument to each soldier who served in Afghanistan, there were tears in his eyes. It was emotional, of course."
With more than 900 television reports spanning almost four years, Leshchinsky, 69, is remembered by many as the face of the Soviet-Afghan war.
Critics have derided him as the "Afghan Nightingale," a regime propagandist who sang the soldiers' praises at the bidding of the Kremlin.
But as the first Soviet reporter to broadcast footage from the battlefield, Leshchinsky was also an instrumental player in the policy shift that led to the Soviet withdrawal a quarter-century ago.
His often graphic reports marked a turning point in Soviet television's coverage of the conflict, which had until then focused on casting soldiers as peacekeepers chiefly engaged in friendly encounters with locals.
Gorbachev's rise to power, combined with mounting disillusionment in Moscow with the war, helped somewhat loosen the Soviet Union's grip on its journalists in Afghanistan.
Just one month after arriving in Afghanistan, Leshchinsky received a phone call from Sergei Lapin, the powerful head of the Soviet broadcasting company, instructing him to film military operations and send the footage to Moscow at least twice a week.
He says Soviet military authorities in Afghanistan immediately followed suit by granting him full, uncensored access to the battlefields.
"It had become obvious that we were bogged down in this war, that we were incurring massive financial, moral, and human losses, and that the war must end," Leshchinsky says. "But it had to be ended in such a way that people would not get the impression we were fleeing, defeated, or retreating. The task was to establish among the public the opinion already held by the leadership: that this war was pointless and needed to end."
Leshchinsky says the second and final stage of the Soviet withdrawal, which stretched over a period of six months, was both an exhilarating and a wretched time for reporters.
For more than two months, he and his team traveled back and forth across the border to cover the pullout, each time parting with homebound soldiers before heading back to the battlefield.
"It was tough emotionally," Leshchinsky says. "For the young men we accompanied on their way out, the war was ending. But we had to go back into war every time, and it was a difficult operation. The fighting continued, there was shelling, we were losing people."
According to official figures, about 520 soldiers died during the withdrawal.
The Soviet army suffered its last casualty on February 10, just five days before the withdrawal was completed. Leshchinsky says he can still clearly picture the soldier's coffin being taken across the border on an armored troop-carrier.
Chaos reigned on the Soviet side, too.
As the pullout deadline neared, anxious parents flocked en masse to the border in the hope of speedily reuniting with their sons.
Instead, Leshchinsky remembers, many ended up lingering there for weeks without news of their children.
"No one even bothered telling parents where and when military units would be arriving," he says. "A huge number of people gathered in [the Soviet-Afghan border cities of] Termez and Kushka, and none of them knew when their sons would arrive. People literally lived at the border for months."
Unlike many veterans, Leshchinsky stops short of calling the war a mistake.
But with the United States poised to withdraw from Afghanistan after its own inconclusive war, the former reporter cannot help ponder on what he calls the futility of foreign military interventions in Afghanistan.
"The result of their stay there, in my opinion, is null; just like the result of our stay there is null," Leshchinsky says. "Maybe it is actually negative because both we and the Americans suffered huge losses. We lost people, equipment, money. And in the end, our image also took a beating."