The earliest known mortar was used by the ancient Egyptians, and was made from gypsum. This form was essentially a mixture of plaster and sand, and was quite soft.
Lime mortar, using quicklime, CaO, was discovered about 4000 BC, about the time the great Egyptian pyramids were built. Lime, CaO3, is heated to release CO2 as a gas, leaving behind CaO. When later mixed with water it forms hydrated, or slaked, lime, which releases heat and slowly dries to a solid Ca(OH)2. The slaked lime is normally fairly plastic and therefore easy to work with. Over time the slake reacts with CO2 in the air to re-form back into CaO3, releasing water in the process. Lime mortars were used thoughout the world, notably by the Roman Empire buildings throughout Europe and Africa.
Cement mortars were first developed by the Roman Empire but did not become widespread in Europe until the 18th century, and did not fully replace lime mortar until about 1930. Lime mortar was slower to harden, but more flexible, making it more compatible with soft old bricks. Cement mortar is less permeable, harder, and more suitable for use with hard modern bricks.