Lions did in fact inhabit parts of Europe in ancient antiquity, such as in Greece until sometime around 100 BCE. Lions thus appear in Greek mythology, such as in the myth of Heracles (or Hercules) and the Nemean Lion. Lions also inhabited regions adjacent to modern Europe, including Caucasia and Northern Africa, until the 10th and 17th century CE respectively. Thus both actual lions and artistic renderings of lions were exchanged in relations between European and Middle Eastern/Africa cultures. Ancient Rome often used captive lions for entertainment, and lions were often given as gifts to the nobility. The menagerie (a precursor to a zoo) of Henry I of England in the 12th century was reputed to have lions. Constant exposure to the concept of lions in the form of art, literature, and physical specimens thus perpetuated the appearance of the fierce beast in European culture, in the form of art and literature.

Sources

Sallares, R. (1991) The ecology of the ancient Greek world, Cornell University Press, p. 401

Blunt, Wilfred. The Ark in the Park: The Zoo in the Nineteenth Century. Hamish Hamilton, 1976, pp. 15-17.

Edit: Look at the much more comprehensive answer above mine

Lions symbolize strength and royalty. They did so from a very early point onwards, especially in the ancient Near East, where they were often depicted, for example, in royal lion hunts. In Europe, we start encountering lions in art from at least the Late Bronze Age onwards. The Mycenaeans -- essentially Late Bronze Age Greeks -- were the first Europeans to depict the lion in art, adopting Near-Eastern motifs such as the lion hunt. The most famous instance of lions in Mycenaean art is the Lion Gate from Mycenae itself, built around 1250 BC: see, among others, R. Hope Simpson and D.K. Hagel, Mycenaean Fortifications, Highways, Dams and Canals (2006) for more details on that.

Because the lion is so common in Mycenaean art (and is commonly associated with royalty in the Near East), it has been suggested that the lion was a symbol for the Mycenaean royal house. There's actually been quite a bit of research on the subject of the lion in Mycenaean art, most notably by Nancy R. Thomas. I found interesting this paper: N.R. Thomas's "The war animal: three days in the life of the Mycenaean lion", in R. Laffineur (ed.), Polemos: le contexte guerrier en Égée à l'âge du Bronze (1999), pp. 297-312. After the fall of the Mycenaean palaces in ca. 1200 BC, Greek figurative art disappears over the course of the twelfth century BC, but when it re-emerges, in full force in the eighth century BC, lions soon enough re-enter the picture.

One of the most interesting early post-Mycenaean uses of the lion in Greek art occurs on the so-called Chigi Vase of ca. 640-625 BC, an example of "Orientalizing" Greek art (specifically, Middle to Late Protocorinthian). In his article "‘Reading the Chigi Vase", published in Hesperia 71 (2002), pp. 1-21, Jeffery Hurwit has argued that the decoration on the Chigi Vase forms a consistent whole, with each of the different scenes on the pot as kind of a comic-book representation of the life of a young aristocrat. On the bottom frieze, young boys hunt hares, while the frieze above depicts young men fighting with a lion. In the top frieze, the men fight the most dangerous prey of all: other human beings. The vase as a whole embodies themes of violence (the hunt, war) and masculinity. It's a very interesting article; you'd do well to look it up (you can get a free JStor account to download three articles or so).

All of this makes one wonder if lions every existed in Europe. While for a long time it was thought that lions never roamed the Greek landscape, evidence has been mounting that suggests that they probably did. We know that lions certainly lived in Anatolia until some point in the past (they may have gone extinct in Anatolia because of the Romans capturing them for use in the arena). An increasing number of lion bones has also been unearthed in Greece that strongly suggest that lions did once live in Greece. For an overview of the relevant evidence, see Nancy Thomas's "A lion's eye view of the Greek Bronze Age", Aegeum (2014), pp. 375-389. There is no evidence that lions ever went farther into Europe than Greece.

Edit: as regards the Near-Eastern aspect, the British Museum has a wonderful collection of Assyrian reliefs that depict lions, including lion hunts, which you might find interesting to examine and compare to later European depictions of lions.

If I may add to the excellent replies by /u/JoshoBrouwers and /u/MontypythFC:

Lions symbolize strength and royalty. They did so from a very early point onwards, especially in the ancient Near East, where they were often depicted, for example, in royal lion hunts. In Europe, we start encountering lions in art from at least the Late Bronze Age onwards.

In western and northern Europe, the Lion wasn't always the symbol of royalty and strength. That function was previously held by a fauve beast native to the regions: the Bear. Bear imagery and bear-related myths are very common among the peoples living in bear habitat throughout the world. I don't have knowledge about North America though; so I'll leave it here for now. There are signs of a circumpolar family of bear-cults from the Saami of Scandinavia to the (many) peoples of northern Siberia, for instance.

Allow me to digress very shortly in order to better show how important bear figures were. In ancient Germanic, Slavic and Celtic cultures the bear played a very important symbolic role. It was associated with virility, strength, and the ability to fight as well as sexual prowess. There is a recurrent myth form among European peoples where a bear-like figure raptures a woman to rape her, thus breeding half-man half-bear heroes often gifted with a specific fate and great martial prowess. Of course you've heard of the berserkers, the Norse warriors whose name meant "bear shirt" -- since they used to wear bear skins to show off their strength and recklessness. Maybe you know the Greek goddess Artemis, the Huntress. There are some who think her name is related to the greek arktos meaning, you guessed, the bear. The same (admitedly speculative) hypothesis applies to the name Arthur - some would see in the mythical warrior/king a resurgence of older bear-like heroic forms of Celtic and Germanic peoples. And of course you have a lot of placenames and personal names derived from the bear/bär root. Bern, Berlin, Bjorn...

In any case, the bear has since been replaced by the lion as the "king of Animals". The French scholar Michel Pastoureau argues that the Roman Catholic Church favored such mythography over the more traditional, pagan bear figures. By chosing the lion over the bear, the Church let the symbol of strength/virility/power be an animal from far away, associated with the glory of the Roman empire above all, and unlikely to be found in the forests of newly converted Germany or northern Europe. Thus there would be no lion worshipping, no offerings, no cult except through approved church imagery, in contrast with the bear ceremonies (still too pagan for the church).

Source: Michel Pastoureau, L'ours (I have mine in Flammarion but I'm pretty sure it has been translated)

If you want more information, the FAQ has a section on this topic here.