The staged rocket design is common now, but at some point in the history of rocket design it must have been revolutionary.
When was the staged design introduced? Was it quickly accepted or did it take a while to become commonplace?
The first multistage rocket is much older then one might think. Its from the 14th century CE.
Huolongchushui or fire dragon issuing from the water (Chinese: 火龙出水; pinyin: huolóngchushui; literally: 'fire dragon out of water') were the earliest form of multistage rockets and ballistic cruise missiles used in medieval China. The name of the weapon was used to strike fear into enemy troops. If the enemy was out of range, the fire dragon had a contingency. Magazine of three rocket driven arrows located within the mouth of the missile. It acted as one of the world's earliest multistage rockets and ballistic cruise missiles, fired at enemy ships in naval battles.
The British scientist and historian Joseph Needham points out that the written material and depicted illustration of this rocket come from the oldest stratum of the Huolongjing, which can be dated roughly 1300–1350 AD (from the book's part 1, chapter 3, page 23).
(Source: Wikipedia/Multistage Rocket)
The texts seem to strongly imply that the rockets were not only theoretical, but actually used in battle.
If you count the arrows as separate stage and not payload, this is a multi-stage rocket.
In Europe, the first multi-staged rocket (and the first description of 3+ stages I could find) was invented by the German (Bavarian) Johann Schmidlap in the 16th century, who described them in his work "Künstliche und rechtschaffene Fewerwerck zum Schimpff", published in 1560 at Johann vom Berg und Ulrich Neuber in Nuremberg (Nürnberg). It was reprinted in 1564, and in 1590/1591 a new edition was made .
This design differs a bit from earlier chinese designs (which were unknown in europe at the time) in that there are multiple stages which are meant for propulsion, and not only a payload that itself is rocket-propelled.
The following illustration show his two- and three-stage concepts:
The work (in the 1564 edition) is available at archive.org 
He might or might not have been influenced by ideas from Conrad Haas, who had similar thoughts.
A good writeup is available in Doru Todericiu, 'Raketentechnik im 16. Jahrhundert' (PDF available ).
Sadly, both the original text and the write-up are only available in German. I could not find good English sources, except that he is credited for the aforementioned achievement by NASA .
I would mention works of Konstantin Tsiolkovsy. I think that he was first, who proposed to use multistage rockets for space flights.
His most important work, published in May 1903, was Exploration of Outer Space by Means of Rocket Devices (Russian: Исследование мировых пространств реактивными приборами).
Tsiolkovsky calculated, using the Tsiolkovsky equation, that the horizontal speed required for a minimal orbit around the Earth is 8,000 m/s (5 miles per second) and that this could be achieved by means of a multistage rocket fueled by liquid oxygen and liquid hydrogen.
Rocket Devices", it was proved for the first time that a rocket could perform space flight. In this article and its subsequent sequels (1911 and 1914), he developed some ideas of missiles and considered the use of liquid rocket engines.
Important new ideas are often thought by more than one person of a single nation. See this page about multistage rockets.
In the 14th century the idea was developed in China and Korea using solid rockets made with gun powder.
Later in Europe this idea apeared in Austria, Germany and Poland as already answered.
Theoretical work was done by at least four individuals:
The first design of a multistage liquid fuel rocket was started in Germany during WWII. But the design of the A9/A10 was never finished and realized. It was the first design of a intercontinental military rocket.
After WWII the first flight tests of a large two stage liquid fueled rocket were done in the USA using the German A4-V2 rocket and the US WAC Corporal as second stage. The combination was called Bumper. Records in height and range were acheived. The first rocket launched from Cape Canaveral was Bumper 8.
The first payload in orbit was launched by the Russian Sputnik rocket. This rocket used parallel staging instead of serial. All engines could be ignited at launch pad and the engine of the second stage did work before and after separation of the boosters. Another variant of the R-7 rocket family, the Vostok was used for the first manned orbit. Even the first moon missions were done using a Vostok variant.
Cyrano de Bergerac wrote in 1657 of traveling to the Moon using staged spaceflight, and even mentioned that after getting most of the way there, the Moon's gravitational attraction would exceed that of Earth's!
Philip Ball reveals the real Cyrano de Bergerac - forget the big nosed fictional character - and his links to 17th Century space flight. Cyrano was a soldier, gambler and duellist who retired from military exploits on account of his wounds around 1639, at the grand old age of 20. But he studied at university and, to judge from the books he went on to write, he was well versed in the philosophical and scientific debates of his day. He designed spaceships to travel to the moon and to the sun. Philip discusses the life and times of Cyrano with Mary Baine Campbell of Brandeis University in Massachusetts.
Journeys to the New World in the seventeenth century were voyages of trade - and ultimately of colonisation. Today, the profit motive has returned to space travel. Efforts to develop spacecraft and to send people into space are increasingly being conducted not just by government agencies but by private companies, in search again of land and minerals. Philip discusses the control of exploitation of space with Patricia Lewis of ICAN, the International Campaign to Abolish Nuclear Weapons.
I ran and grabbed the arm of the soldier who was lighting the fire. I tore the fuse away from him and, furious, threw myself into my machine to break down the contraption surrounding it. But I was too late. Hardly had I stepped inside when I found myself propelled into the clouds. I was terrified, but my mind was not too upset for me to remember all that happened at that moment. I can tell you, then, that the fire burned out a bank of rockets (which had been linked together in rows of six with a hook at the edge of each set of half-dozen). Another stage ignited, then another, so that the danger in the gunpowder was left behind as it burned. When the material was used up, the scaffolding was gone. I was thinking that all I had left to do was ram my head against some mountain when I felt (without moving in the slightest) that I was still going up. My machine separated from me, and I saw it fall back to earth.
Over the centuries many have thought about the prospects of space travel. In 1657 Cyrano de Bergerac wrote a story called “Voyage dans la Lune” where a machine flies to the Moon using a principle of rocket staging (discussed below). This was a remarkable concept and way ahead of its time.