Pagan historically meant the worship of many Gods, and was the common religious worship of ancient times. Heathen, a similar term, meant the folk beliefs and worship of the very rural people living in the "Heath". Polytheistic worship made tremendous sense before Reason and Observation began to discern patterns in Nature. The various aspects of Nature and the seemingly unrelated events in Human life prompted a belief that these various forces were representative of various, competing supernatural forces with Human-like minds and intentions.
This attitude instilled a reverence and awe of Nature, and desire to observe and understand the material world in a Spiritual context.
While there were a few brief experiments with monotheism before the Judeans aka the Hebrew people, the Tribe or extended family of Jacob (Israel) serves as Western Civilizations' foundation for Monotheistic thought, but the original Tribes of Israel believed in a henotheistic theory of the situation. The God of Israel had created the world, and the Jewish People. Somehow other Gods exist for OTHER tribes and those Gods are legitimate enough that your God and theirs can have contests through their adherents on Earth. This evolves into complete Monotheism as herding gives way to an urban life over time.
After the introduction of Greek philosophy, Jews became more interested in what happened to the personality after death. Previously, all Jewish religious thought was focused on living a good life rather than questing for the hereafter. The "World to Come" as it was known, was a shadowing place the living could not comprehend. Heretical sects of Jews organized around Messianic and apocalyptic concepts, including the Gnostic Jews and early Christians, would withdraw from the world to await it's end and the beginning of a better one.
Zarathustra, AKA Zoroaster (in Greek), (2nd millennium BCE or so, somewhere in Iran / Iraq / Afghanistan/ Persia), taught the visible world was a lie, created by a false God, who needed to be resisted by inward seeking meditation and prayer to pierce the veil and receive "gnosis" or immediate, overwhelming experiences of the real God. "One of the greatest evils in the time of the prophet was the tendency of the populace to adore and worship God's manifestations or created elements." (S.A. Kapadia, 1905)
These beliefs appear, but more subdued and without the malevolence inherent in Zarathustra's Real God vs Evil God system, in Plato's concept of the Material World being a mere reflection of the real, spiritual world of First Forms. The Soul forgets all it knows at birth, and struggles against this ignorance to remember and return to the Heaven from which it came. Know Thyself is the Magick Formula, still so vital, it never goes out of style.
The striking difference, and it reoccurs throughout history, is in Zarathustra's world, Man is held back by an Evil, false God, who is almost as powerful as the Creator, Real God with whom he contests for Earth. The Catholic Church would utilize this model. In Plato , Neoplatonism and the world of the Qabalists, there is only God, and ignorance holds Man back, not any powerful malevolence. If there is no progress towards fulfillment, we have only our own efforts to blame.
The Gnostics practiced Asceticism, withdraw from Earthly pleasure to concentrate on the Spiritual world within. If the world we see is a prison of the Flesh, then it's spiritual ruler must be equally Evil, and the True God of the Spiritual is not the Lord of the Earth, who must be his opposite, the Devil. This is the opposite of the mainstream Jewish view that the material world is the "fruit" of God, and also explains their exclusion from the towns and cities, creating desert settlements.
From these Judeans, Gnostic foundations Christianity grows, with it's various beliefs in the identification of Jesus with his Father, and his Holy Spirit forming a Three-In-One God. Christian sects continue to argue this point, called Trinitarian monotheism, as being a form of monotheism. Isaac Newton could not believe that the numerical equation 1=3 made sense, and was exempted from taking religious oaths during his tenure at the University. If you also count the Devil as part of the Christian God system, there are at least two sides (three if Man's Free Will is considered) and 5 entities, 6 if you count the Institution of the Church as well, in this monotheistic religion. Once we look at Catholicism, with it's Virgin and Saints....we have a lot of Spiritual beings populating the Heavens.
Even Jewish monotheism evolved, and the various NAMES and titles of God in different books gives us clues to when they were written. While God was ONE, HIS moods were many, and calling HIM for War was different than begging HIM to save the life of a child or make a barren woman bear child.
Since everyone except the Jews believed in many Gods in the ancient world, the word Pagan had little meaning until the rise and dominance of Christianity. The Greek cultural tide had overwhelmed Judea, and the Roman political machine which followed filled the land with soldiers and travelers from those Empires, and the new Christians sought to distinguish these people and their influence as "Pagan", meaning believing in the Greek and Roman Gods. When these Christians inherited the Empire, they used that term to describe all people's they met who natively believed in a pantheon of Gods, such as the Germanic, Scot, Welsh, Pict etc. barbarians they encountered. So "Pagan" was expanded to include the Druid and Scandinavian, as well as Greek and Roman Gods.
In Modern Times, Pagan is used a religious label by followers of Wicca, Neopaganism, Asatru, Odinism and Native American Shamanism, to contrast with the world's three dominant faiths of Christianity, Islam and Judaism. It is not an exclusive term, so someone may be Pagan and Wiccan, or even a Celtic Christian Pagan. Jewitches are common, as are Buddhist Pagans. It is an inclusive term, rather than a fence to exclude those open to worshiping together.
Resources: http://www.sacred-texts.com/zor/toz/toz04.htm; http://www.nydailynews.com/news/national/kansas-killer-worshipper-neo-pagan-odinism-article-1.1757496 ; http://press.princeton.edu/chapters/p9814.pdf ;