According to the Big Bang theory, the universe was born around 13.7 billion years ago. A few hundred million years later the first stars were formed, and around 13.6 billion BC the Milky Way Galaxy began to take shape. Our Solar system was formed around 4.5 billion BC, with the earliest known microbes existing around 3.5 billion BC. Humans a rived on the scene less than 2 million years ago.
When did the very first humans look at the night sky and recognize patterns in the stars, and understand that these patterns move in a consistent manner? It's impossible to be sure but it's probably safe to assume that if a human is clever enough to use tools, control fire and navigate reasonable distances, then s/he is clever enough to notice the patterns and movements of the stars.
One of our ear list recognizable ancestors is Australopithecus afarensis, which lived around 3.7 to 2.9 Ma. This primitive creature may have been the first to use stone tools , but most likely had not developed any significant language (they may have communicated in a similar way to modern apes ).
Homo erectus lived from about 1.8 millions years ago to about 70,000 years ago. Widely (but not universally) thought to be an ancestor of modern humans, Homo Erectus walked truly upright, used more advanced tools, and may have used fire to cook meat. They also probably developed primitive symbolic communication (a precursor to modern language).
Homo sapiens probably evolved around 250,000 years ago, although recent discoveries may push that time back as far as 400,000 years.
Agriculture began around 10,000 years ago, and with agriculture comes astronomy. Early farmers needed to understand of the annual "star calendar" in order to successfully plant crops and perform other date-dependent tasks.
The early development of religion was heavily influenced by the perceived importance of celestial objects. Early cultures focussed first on the Sun, with many having Sun gods. With the Sun's status as a supernatural life-giver, it follows that other, equally mysterious objects such as stars and planets would have been shown similar reverence.
Examples early cultures that showed some proficiency in astronomy: