Both the Feast of All Saints and the Feast of All Souls evolved in the life of the Church independently of paganism and Halloween. However, elements of pagan practices were perhaps "baptized" by some cultures or attached themselves to the celebration of All Saints and All Souls.
Let us first address the Feast of All Saints. The exact origins of this celebration are uncertain, although after the legalization of Christianity in 313 a common commemoration of the saints, especially the martyrs, appeared in various areas throughout the Church. For instance in the East, the city of Edessa celebrated this feast on May 13; the Syrians, on the Friday after Easter; and the city of Antioch, on the first Sunday after Pentecost. Both St. Ephrem (d. 373) and St. John Chrysostom (d. 407) attest to this feast day in their preaching. In the West, a commemoration for all the saints also was celebrated on the first Sunday after Pentecost. The primary reason for establishing a common feast day was because of the desire to honor the great number of martyrs, especially during the persecution of Emperor Diocletian (284-305), the worst and most extensive of the persecutions. Quite simply, there were not enough days of the year for a feast day for each martyr and many of them died in groups. A common feast day for all saints, therefore, seemed most appropriate.
In 609, the Emperor Phocas gave the Pantheon in Rome to Pope Boniface IV, who rededicated it on May 13 under the title St. Maria ad Martyres (or St. Mary and All Martyrs). Whether the Holy Father purposefully chose May 13 because of the date of the popular celebration already established in the East or whether this was just a happy coincidence is open to debate.
The designation of November 1 as the Feast of All Saints occurred over time. Pope Gregory III (731-741) dedicated an oratory in the original St. Peter’s Basilica in honor of all the saints on November 1 (at least according to some accounts), and this date then became the official date for the celebration of the Feast of All Saints in Rome. St. Bede (d. 735) recorded the celebration of All Saints Day on November 1 in England, and such a celebration also existed in Salzburg, Austria. Ado of Vienne (d. 875) recounted how Pope Gregory IV asked King Louis the Pious (778-840) to proclaim November 1 as All Saints Day throughout the Holy Roman Empire. Sacramentaries of the 9th and 10th centuries also placed the Feast of All Saints on the liturgical calendar on November 1.
According to an early Church historian, John Beleth (d. 1165), Pope Gregory IV (827-844) officially declared November 1 the Feast of All Saints, transferring it from May 13. However, Sicard of Cremona (d. 1215) recorded that Pope Gregory VII (1073-85) finally suppressed May 13 and mandated November 1 as the date to celebrate the Feast of All Saints. In all, we find the Church establishing a liturgical feast day in honor of the saints independent of any pagan influence.
Now for the pagan connection: November 1 marked Samhain, the beginning of the Celtic winter. (The Celts lived as early as 2,000 years ago in England, Scotland, Wales, Ireland and northern France.) Samhain, for whom the feast was named, was the Celtic lord of death, and his name literally meant "summer’s end." Since winter is the season of cold, darkness and death, the Celts soon made the connection with human death. The eve of Samhain, October 31, was a time of Celtic pagan sacrifice, and Samhain allowed the souls of the dead to return to their earthly homes that evening. Ghosts, witches, goblins and elves came to harm the people, particularly those who had inflicted harm on them in this life. Cats too were considered sacred because they had once been human beings who had been changed as a punishment for their evil deeds on this earth.
To protect themselves from marauding evil spirits on the eve of Samhain, the people extinguished their hearth fires and the Druids (the priests and spiritual teachers of the Celts) built a huge new year’s bonfire of sacred oak branches. The Druids offered burnt sacrifices — crops, animals, even humans — and told fortunes of the coming year by examining the burned remains. People sometimes wore costumes of animal heads and skins. From this new fire, the home hearths were again ignited.
Particular ethnic groups developed their own lore that was merged with the celebration. In Ireland, people held a parade in honor of Muck Olla, a god. They followed a leader dressed in a white robe with a mask made from the head of an animal, and begged for food. (Ireland is also the source of the jack-o’lantern fable: A man named Jack was not able to enter heaven because of his miserliness and he could not enter hell because he played practical jokes on the devil; so he was condemned to walk the earth with his lantern until Judgment Day.)
The Scots walked through fields and villages carrying torches and lit bonfires to ward off witches and other evil spirits.
In Wales, every person placed a marked stone in the huge bonfire. If a person’s stone could not be found the next morning, he would die within a year.
Besides the Celtic traditions in place, the Roman conquest of Britain in AD 43 brought two other pagan feasts. Feralia was held in late October to honor the dead. Another autumn festival honored Pomona, the goddess of fruits and trees; probably through this festival, apples became associated with Halloween. Elements of these Roman celebrations were combined with the Celtic Samhain.
With the spread of Christianity and the establishment of All Saints Day, some of these pagan customs remained in the English-speaking world for All Hallows Eve (or Halloween, All Saints Eve), perhaps at first more out of superstition, and later, more out of fun. Nevertheless, All Saints Day clearly arose from a genuine Christian devotion.