Russian space agency Roscosmos made the announcement on its website on Friday, without providing a cause for his death. Russian media earlier reported that Leonov had had health issues for several years.
NASA broke into its live televised coverage of a spacewalk by two Americans outside the International Space Station to report Leonov's death.
"A tribute to Leonov as today is a spacewalk," Mission Control in Houston said.
Leonov was born in 1934 in a large peasant family in western Siberia. Like countless Soviet peasants, his father was arrested and shipped off to Gulag prison camps under Soviet dictator Josef Stalin but he managed to survive and reunite with his family
The future cosmonaut had a strong artistic bent and even thought about going to art school before he enrolled in a pilot training course and, later, an aviation college. Leonov did not give up sketching even when he flew into space, and took colored pencils with him on the Apollo-Soyuz flight in 1975 to draw.
That mission was the first one between the Soviet Union and the United States and was carried out at the height of the Cold War. Apollo-Soyuz 19 was a prelude to the international cooperation seen aboard the current space station.
But where Leonov staked his place in space history was on March 18, 1965, when he exited his Voskhod 2 capsule secured by a tether.
Spacewalking always carries a high risk but Leonov's pioneering venture was particularly nerve-wracking, according to details of the exploit that only became public decades later.
His spacesuit had inflated so much in the vacuum of space that he could not get back into the spacecraft. He had to open a valve to vent oxygen from his suit to be able to fit through the hatch.
Leonov's 12-minute spacewalk preceded the first U.S. spacewalk, by Ed White, by less than three months.
On his second trip to space ten years later, Leonov commanded the Soviet half of Apollo-Soyuz 19.
The cosmonaut was well known for his humor. Once the U.S. Apollo and Soviet Soyuz capsules docked in orbit around Earth in July, 17, 1975, Leonov and his Russian crewmate, Valeri Kubasov, welcomed the three U.S. astronauts — their Cold War rivals — with canned borscht disguised as Stolichnaya vodka.
"When we sat at the table, they said: 'why, that's not possible'," Leonov recalled in 2005. "We insisted, saying that according to our tradition we must drink before work. That worked, they opened it and drank (the borscht) and were caught by surprise."
The cosmonaut turned 85 in May. Several days before that, two Russian crewmembers on the International Space Station ventured into open space on a planned spacewalk, carrying Leonov's picture with them to pay tribute to the space legend. They said "Happy birthday!" to Leonov before opening the hatch and venturing out.
Leonov's modern-day successor, Oleg Kononenko, who was one of the two Russians on that spacewalk, told Rossiya-24 television on Friday that Leonov tuned in to hear their congratulations from space.
"We were going to stop by Alexei Arkhipovich (Leonov) after our return and give him our space souvenirs, but you see it wasn't meant to be," Kononenko said. His crew returned to earth at the end of June when Leonov was already unwell.
Kononenko spoke fondly of the Soviet space pioneer, saying that he was a frequent guest at send-off ceremonies for space crews in Star City and at the cosmodrome in Baikonur, Kazakhstan.
"We had this tradition that he would give cosmonauts pep talks before they board the spacecraft," Kononenko said. "We all looked forward to that, always thought about it and always wanted Leonov to be the one to send us off into space."
Leonov — described by the Russian Space Agency as Cosmonaut No. 11 — was an icon both in his country as well as in the U.S. He was such a legend that the late science fiction writer Arthur C. Clarke named a Soviet spaceship after him in his "2010" sequel to "2001: A Space Odyssey."
Kremlin spokesman Dmitry Peskov on Friday relayed the Russian president's condolences for Leonov's family saying that Vladimir Putin and the cosmonaut knew each other well and often saw each other.
"Putin always admired Leonov's courage and thought he was an extraordinary man," Peskov told Russian news agencies.
Messages of condolences poured from around the globe.
NASA on Friday offered sympathy to Leonov's family, saying it was saddened by his death.
"His venture into the vacuum of space began the history of extravehicular activity that makes today's Space Station maintenance possible," NASA said on Twitter.
Leonov, who will be buried on Tuesday at a military memorial cemetery outside Moscow, is survived by his wife, a daughter and two grandchildren.