In fact, scientists believe that it took up to 200 million years for the first stars to emerge from an obscure soup of matter.
As current telescopes aren't sensitive enough to observe the light from these stars directly, astronomers have been looking for indirect evidence of their existence instead.
Now a team of scientists has managed to pick up a faint signal from these stars with a radio antenna the size of a table top, called EDGES.
The impressive measurement, which opens a new window on the early Universe, shows that these stars emerged about 180 million years after the Big Bang.
Models have shown that the first stars that lit up the Universe would have been blue and short-lived, producing a bath of ultraviolet light.
The earliest observable signal of this cosmic dawn has long been thought to be an "absorption signal" - a dip in brightness at a particular wavelength - caused by this light passing through and affecting the physical properties of clouds of hydrogen gas, which is the most abundant element in the Universe.
We know this dip should be found in the radiowave part of the electromagnetic spectrum, at a wavelength of 21 centimetres (8.2 inches).
This was all predicted by theory.
But in practice, the signal is extremely challenging to find.
This is because it overlaps with many other signals in this region of the spectrum which are much stronger - such as common frequencies on the FM radio dial and radio waves from other events in our galaxy.
The reason the team eventually succeeded was partly down to the experiment's sensitive receiver and small antenna, which lets you cover a large area of the sky more easily.
To be sure that that any dip in brightness they found came from starlight in the early Universe, the team looked at an effect known as the Doppler shift - you will have experienced this as a lowering of pitch when a siren passes by at speed.
Similarly, as all galaxies are receding away from us due to the expansion of the Universe, light is shifted to redder wavelengths. Astronomers call this effect " redshift".
Redshift tells scientists how far away a certain gas cloud is from Earth and how far back in cosmic time the light from it was emitted.
In this case, any shift in the dip in brightness expected at 21 centimetres wavelength would give an indication of how the gas is moving and how far away it lies.
The team measured a dip that covered a range of times in the cosmos - most dramatically back to when the Universe itself was only 180 million years old, compared to its grand age today of 13.9 billion years. This was the light from the very first stars.
Dark matter twist
The story doesn't end there. The team was surprised to find that the amplitude of the signal was more than twice as large as predicted. This suggests that the hydrogen gas was much colder than expected of the background radiation.
These findings, published in another paper in Nature, have thrown a spanner in the work of the theoretical physicists.
This is because the physics suggests that at this time in the Universe, it would have been easy to heat gas but difficult to cool it.
In order to produce the extra cooling needed to explain the signal, the authors argue, the gas must have interacted with something even colder. And the only thing known in the early Universe colder than this cosmic gas is dark matter.
In fact, theorists must now decide whether they should extend the standard model of cosmology and particle physics to explain this effect.
We know that dark matter is five times more common than normal matter but we don't yet know what it is made of.
Several options for particles that could make up dark matter have been proposed, with the favourite candidate being the Weakly Interacting Massive Particle (WIMP).
The new research, however, suggests that the dark-matter particle would not be much heavier than a proton (which makes up the atomic nucleus along with the neutron). This is well below masses predicted for the WIMP.
The analysis also suggests that the dark matter is colder than expected, and opens the exciting possibility of using "21-centimetre cosmology" as a new probe of dark matter in the Universe.
Further discoveries with more sensitive receivers and less complications from terrestrial radio interference - which could be achieved by placing an interferometer on the dark side of the moon - could unveil more details about the nature of dark matter, maybe even probing the speed at which it is moving.
This comes at an opportune time for radio astronomers, who are developing the next generation of giant networks of radio telescopes or interferometers in Australia and South Africa called the Square Kilometre Array as well as other cutting-edge experiments dedicated to studying the cosmic dawn.
It's an exciting time to be a scientist.