Long ago, people believed cats had 9 lives. (As shown in ice age)
When and where did that belief come from?
It may not be possible to trace the exact origins of the phrase that a cat had nine lives. Nevertheless there are a few sources from which we can find a possible origin of cats having nine lives.
First of all, it may have an Egyptian (and thus the oldest believed) origin as the following statement reveals:
The old belief that a cat has nine lives goes back to ancient Egypt. The cat-headed goddess, Bast (or Ubasti), was associated with the benevolent aspect of Hathor, the Lioness, and was said to have nine lives. The Egyptians did not fear the cat, but rather reverenced it, and they elevated cats far above the role of domestic pet. To the Egyptians, the cat was transformed from mouse catcher to supreme deity, the "Sayer of Great Words." The Egyptian word for cat was Mau, which is at once an imitation of the animal's call and the nearly universal human cry for mother. Cats came to be worshipped with such intensity that the wanton killing of a cat was punishable by death. - Encyclopedia of the Unusual and Unexplained: Superstitions, Strange Customs, Taboos, and Urban Legends.
The follow point could be taken into consideration here:
Nine is also a magic number- and this could be partly why cats are attributed with having nine lives, because they have been both worshipped and feared throughout the ages for being magical. The ancient Greeks said that the number nine referred to the trinity of all trinities- and is a mystic number which invokes tradition and religion. - Cats have 9 lives: the facts behind the myth.
There is also the Celtic mythological legend of the Cat Sìth, which offers us its own possibility of being the source of this belief that cats had nine lives!
The Cat Sìth is a fairy creature from Celtic mythology, said to resemble a large black cat with a white spot on its chest. Legend has it that the spectral cat haunts the Scottish Highlands. The legends surrounding this creature are more common in Scottish folklore, but a few occur in Irish. Some common folklore suggested that the Cat Sìth was not a fairy, but a witch that could transform into a cat nine times.
Some people believed that the Cat Sìth was a witch that could transform voluntarily into its cat form and back eight times. If one of these witches chose to go back into their cat form for the ninth time, they would remain a cat for the rest of their lives. It is believed by some that this is how the idea of a cat having nine lives originated. - Wikipedia.
More on cats in Celtic folklore can be read here: Cats in Celtic Folklore.
Some believe the origins stem from William Shakespeare's play Romeo and Juliet:
Tybalt: What wouldst thou have with me?
Mercutio: Good king of cats, nothing but one of your nine lives.
There is also an ancient proverb of unknown provenance:
"A cat has nine lives. For three he plays, for three he strays, and for the last three he stays."