"What was the first religion ever established and recorded in history?"

Difficult because their was religion thousands of years before people began writing.

Religion has always been part of society.  I do not know of any civilizations or societies that existed without religion.  Communist countries have tried, but people held to the old ways & worshipped in secret.

The first religion involved the Mother Earth Goddess or the Venus Figurines, associated with prehistoric cultures.  This was a female form, usually the torso, with large or even multiple breasts & enlarged (pregnant) stomach.  They later refined the image to include an actual human-like form; head & legs.  The breasts & pregnant stomach were still a requirement.  The initial ones were carved from wood & they progressed to those shaped from stone.

Recorded history begins with the invention of writing.  Any time before that is classified as pre-historic.

People started writing about 5500 years ago or 3500 BC.

The Mesopotamians & Ancient Egyptians were the first known to have written.

The Ancient Minoans of Crete began writing about 3000 BC.

The Hittites of Anatolia (modern Turkey) began writing about 2000 BC.

The Chinese began writing about 1500 BC.

So the first recorded record of religious beliefs were found in Mesopotamia (Iraq) & Ancient Egypt.

They used soft clay blocks or tablets to write on, which were then baked in an oven or by the Sun; so unless ground into dust, nothing will destroy it.  Writing on a wood slab is not likely to have survived in most climates.

For something to be "recorded in history," it needs to be written down.  History is the period that occurs after the invention of writing, anything before that is "prehistoric."  So, who invented writing?  Sumerians, in modern-day Iraq.  Their writing involved making impressions in clay with a wedge-shaped stylus, called "cuneiform."  Writing changed the world.  Their religion is the first one in history because they were the first to put stylus to clay and "record" it.  (Of course, there was religion long before Sumer.)

What was Sumerian religion like?  It was pretty developed.  They had temples and offerings - we know this from their leftover receipts and documents:

Caption:

This cuneiform text dates back to the 6th year of prince Lugalanda who ruled about 2370 B.C. in southern Mesopotamia. It is an administrative document concerning deliveries of three sorts of beer to different recipients (to the palace and to a temple for offerings) and gives the exact quantities of barley and other ingredients used in brewing. Credit: Max Planck Society

The Sumerian Creation myth begins like this:

In the first days when everything needed was brought into being,
 In the first days when everything needed was properly nourished,
 When bread was baked in the shrines of the land,
 And bread was tasted in the homes of the land,
 When heaven had moved away from the earth,
 And earth had separated from heaven,
 And the name of man was fixed;
 When the Sky God, An, had carried off the heavens,
 And the Air God, Enlil, had carried off the earth . . .    (Wolkstein 4)

Sumer had their own pantheon of Gods and Goddesses and rituals. 

One of the most fascinating things about Sumerian religion, that many people do not know, is that their myths show up again.  Abraham came from Ur, a city in Sumer, and scholars believe that the Sumerian religion had a heavy influence on the Hebrews.  Take, for instance, the Creation of Man, the Fall, and the Flood, according to Sumer:

1. In the Sumerian story, Enki, the water god, and Ninhursag, the mother goddess, are supposed to have created the first man from clay, which they mixed with the blood of a rebellious god. Being angry with humans, they withheld all hope of immortality from them. The gods determined to destroy mankind with a flood, but saved a few so that they and their descendants could serve the immortals.

2. In the Babylonian creation myth the primordial world had only the "two waters" (fresh and salt) until the birth of the gods. Marduk, king of the gods, defeated Tiamat, the goddess of chaos, split her in two, and then created heaven and earth from the two halves, and created humans from the blood of Tiamat’s monster. "Chaos" could be read as similar to the biblical "without form and void". Chaos also figures in Greek mythology as the material from which the earth was made, even before the creation of the gods.

3. The fall of Adam is paralleled by a Persian myth in which Ahriman, or Angra Mainyu (the spirit of darkness and evil), acting through a serpent, causes the first man to fall into knowledge of good and evil. This story is also represented, with variations, in many myths of the Middle East. Babylonian carvings show a man, a woman, a serpent, and a tree. The "Tree of Knowledge" or "Tree of Life" is an almost universal element of Middle Eastern and North African mythology.

Those three points came from this site.  Did the Jews (and later, by default, all the Abrahamic religions) rip off the Sumerians?  You be the judge!  :)

hello

          even though Adam and Eve rebelled and fell,at first they were obedient and without sin. they would have believed everything GOD spoke to them about. believing GOD and HIS TRUTH is religion.

     Cain no doubt,knew a lot,and probably believed  a lot but his soul was dead and he was in rebellion

against GOD and unsaved.

      he would have had many years to have learned from his parents[long life spans] and since Abel was saved, he was under the hearing of the GOSPEL also.

      GOD decided who became saved, but religion was present as soon as GOD was present with man.