Although Lovecraft's name has become inexorably bound with that of his creation, Cthulhu, the great ancient god, Cthulhu itself only appeared in a major role in one Lovecraft story, "The Call of Cthulhu."  Needless to say, the impact of that short story (published in 1928 by the magazine Weird Tales) is such that it is frequently considered one of the most influential short stories ever written.

Lovecraft's Cthulhu mythos arrived in his short story fully formed, and being discovered by a contemporary researcher.  "The Call of Cthulhu" is presented as a nested series of stories, not unlike the structure of Mark Z. Danielewski's House of Leaves.  The story was found by the narrator in manuscript form among the papers of a Boston anthropologist (Thurston), who himself found the story in the notes left behind by his grand-uncle (Angell).

The manuscript is divided into three parts.  In the first part, "The Horror in Clay," the narrator describes a small black statue of the horrible Cthulhu.  The statue was created by a sculptor at a Rhode Island arts college, who created it to describe the terrible beast he was seeing in his dreams.

In the second part, "The Tale of Inspector Legrasse," the anthropologist's grand-uncle talks about the last time he heard the name Cthulhu.  This involved a strange cult in New Orleans, and a statue similar to the one found among the papers.  

This is when we first learn of the cult of Cthulhu, the sleeping god who lies in the remains of his mighty sunken city deep beneath the waves, waiting to be reborn.  The cult of Cthulhu is scattered across the globe, and the fire of Cthulhu worship is largely kept alive by obscure and "heathen" tribes of non-white people in places like Greenland and Arabia.

In the third part, "The Madness From The Sea," Thurston learns of a ghost ship with a lone survivor, and recognizes the story as being connected to the Cthulhu cult.  He is then presented with another manuscript by the sailor (Johansen), about a secret island which the sailors discovered.  In exploring the island, they released Cthulhu from his prison, but then apparently ran him over with their ship and temporarily damaged the god in a head-on collision.  Although Cthulhu begins to re-form immediately, they are able to take advantage of his temporary confusion in order to flee.

For such a short work, the structure of "The Call of Cthulhu" is, as you can see, surprisingly complicated.  It's difficult to understand why Lovecraft would put his narrative eggs in so many different baskets, so to speak, except that it lends the story an air of legitimacy.  It also provides an interesting contrast, between the mythic and grotesque monster story on one hand, and the dry academic world of manuscripts and scholarly references on the other.

I always enjoy re-reading "The Call of Cthulhu," but you definitely have to be in the mood for it.  For better or worse, I can think of no other author so willing to use words like "rugose" and "squamous."