Technically, cosmic horror stories have existed for as long as humans existed and created myths about the world. around the world there have always been myths and belief systems that, in contrast to ones that involve personal, approachable gods and benevolent universes, there are as many belief systems that have mind shattering, impersonal, or inscrutable gods who required human suffering to maintain the status quo of the universe, and nothing else.
However, the thing about Lovecraft, his antecedents, contemporaries, and literary descendants, is that at the time of his writings (and to an extent still now) people consider their places in the universe as something of significance, either due to religious belief or simple egotism. In a materialistic, purely mechanistic conception of reality, he wrote of a world where the "gods" of old still existed, that they still waited for their ragnaroks or for their snake-dicked skeleton monsters to climb out of the stars and devour earth.
And on a primal level, cosmic horror scares because it reminds us that we can conquer and prosper all that we want, Nature and the forces of creation will still go about their business whether it wipes out all human life or not.