Gunpowder (what we now call ‘black powder’) was first invented in China around in the ninth century and it was quickly put to use in firecrackers and other fireworks. The first ground based rocket we definitely know about was built in 1264, it powered a 'ground rat' that terrified the emperor's mother at a feast held in her honour. When the first flying rockets were made isn't clear but they were certainly standard issue for the Chinese army by the mid-14th century.
A solid fuel rocket has its fuel and oxidant mixed together as fine powders and then pressed in to a solid 'cake'. Once it has been lit it will carry on burning until it is used up. In a black powder rocket the fuel is carbon and the oxidant, potassium nitrate. Sulphur acts as a secondary fuel and also catalyses the reaction. In the Ariane 5 solid fuel boosters the fuel is aluminium powder, the oxidant, ammonium perchlorate and polybutadiene acts as a binder to hold the mixture together.
Until the early 20th century rocket motors were never more than a few percent efficient. The problem is that a simple rocket uses only the pressure difference between the combustion chamber and the ambient pressure outside to drive the rocket forward:
The result is that huge amounts of high pressure, high temperature exhaust is thrown out but that it carries with it massive amounts of energy in the form of gas pressure and heat. All of this goes to waste.
Animation of a simple nozzle-less motor: