Записи о Ктхулху обрывочны, но, похоже, он был порождён в мире Вурл, в двадцать третьей туманности. Позже Он бродил зеленой двойной звездой Хотх, где совокупился с существом по имени Идх-йаа, дабы породить Великих Древних Гхатанотхоа, Йтхогтха, и Тсог-Оммога. Далее, Ктхулху и его потомство полетели на Сатурн, откуда сошли на Землю.

По Их прибытии, Ктхулху и его свита на острове в Тихом Океане построили огромный каменный город Р'лиэх. Сначала, потомству Ктхулху сопротивлялись Древние, обитавшие на земле миллионы лет до прихода Ктхулху. После войны, в которой потомки Ктхулху разрушили все города Древних, оба лагеря объявили мир и согласились не мешать друг с другу.

Засим, Ктхулху и его потомки многие годы наслаждались свободой в этом мире, но скоро они впали в период глубокого ожидания. В течение миллионов лет человечество медленно развивалось. Ктхулху говорил с сими новыми существами в их снах, сообщая им, где находятся статуи с его образом, кои он принёс со звёзд. Так зародился культ Ктхулху. Но однажды черный Р'лиэх постигло бедствие. Возможно, это была месть неизвестных божеств или изменения в звёздах, луне, отделённых от Земли (хотя считается, что слуги Ктхулху знали бы об этом). Время сей катастрофы также неведомо; согласно доктрине культа, это произошло после зарождения его первых культов, другие считают, что это случилось задолго до начала развития человечества. Без причины, город Р'лиэх погрузился в воды Тихого Океана, захлопнув Ктхулху и его потомков как в ловушке. Вода заблокировала большинство их телепатических сигналов, исключив любой контакт с их слугами кроме как через случайные сны. Ктхулху не мог ничего сделать, и ждёт, пока звёзды не установятся в надлежащем порядке; лишь тогда он освободится из заключения.

С тех пор, могила Ктхулху время от времени подымалась из воды, освобождая Ктхулху на краткие периоды. Всякий раз, после нескольких дней или недель, Р'лиэх снова погружался обратно в море. Однако придёт день, когда черный город не вернётся к морскому дну. Тогда Ктхулху будет убивать и метаться по всему миру.

Культы Ктхулху широко распространены; следы его поклонения остались на Гаити, в Луизиане, на Юге Тихого Океана, в Мехико, Аравии, Сибири, К'н-йан, и Гренландии. Бессмертные жрецы поддерживали культ где-то в горах Китая, но истинный центр культа был расположен где-то в Аравии, около Ирема. Первая работа Профессора Анжелла и его преемников дала много информации о культах.

В основном этот культ остался тайным, но на Гавайских островах всё ещё ходят легенды о Кана-лоа, злом боге-кальмаре, который заключён в преисподней. Ритуалы Ктхулху часто исполняются близ океана или большого залива, и считается, что Хэллоуин - один из его высших празднеств. Ходят слухи, что Ктхулху - просто высший жрец Йог-Сотхотха. Некоторая вражда существует между Ктхулху и его братом , Невыразимым Хастуром. Однако никто не знает из-за чего возник конфликт между ними.

В некоторых текстах, Ктхулху назван водным элементалом, несмотря на то, что океан блокирует его телепатические сигналы к человечеству. Рукопись Сассех упоминает Ктхулху, как проявление Ньйарлатхотепа, хотя никакой другой источник не интерпретирует его таким образом. Франсис Ланей попытался связать Ктхулху Куиха-Айар с богом войны Хуитзилопохтли. Это явная несуразица; Хуитзилопохтли - бог Ацтеков и он вовсе не похож на Ктхулху. Наконец, некоторые провели параллели между Ктхулху и К'тхулу Соухисом, высшим жрецом Му, который сбежал в Южную Америку. Некоторые принимают любую из этих гипотез.