[T]he Karnids had originally been a nomadic desert folk who worshipped Stone, Salt, and Dune. Then a holy man had come to them preaching of a true world beyond the harsh one evident to their senses, an eternal place where death itself would die. The gateway to it, he said, was a black rock on the shore of a vast inland sea. Then he had died. His people continued to make pilgrimages to the rock for a millennium, waiting for his return,
– Jame's narration, The Sea of Time, "Chapter XIX: A Walk into Shadows", I
The Karnids began as the followers of a holy man, their prophet. He said the gateway to the true world, where death would die, was through the Kencyr temple at Langadine. The Karnids began making pilgrimage to it.
In the finial years of Langadine, King Lainoscopes got tried of the Karnids, and tried to supress their woship by breaking up the temple. When he couldn't, he built a new palace over it. Soon after, both Langadine and the temple were destroyed.
After that, the Karnids wandered for a long time, 
↑The Sea of Time, "Chapter IV: Red Dust" — "riders also in black, cheches concealing all but hard, bright eyes set in sun-dark faces. 'Karnids,' Brier snapped."
↑The Sea of Time, "Chapter XIII: Dreams and Nightmares", I — "a Karnid's black robe and cheche, the tail end of the latter wrapped around his face."
↑The Sea of Time, "Chapter XI: Night in a Lost City", I — " 'they make pilgrimage to it, or did until King Lainoscopes came to power and quickly grew tired of their frenzied worship. A stickler for order, he, […] Lainoscopes tried to break up the rock. Failing that, he built it into the foundation of a new tower.' "
↑The Sea of Time, "Chapter XIX: A Walk into Shadows", I — "a grief-stricken Tishooo had subsequently smashed the Langadine temple. 'The Karnids wandered for a long time after that,' Shade was saying. 'Eventually, they settled at what came to be known as Urakarn.' […] 'Probably because they found another Kencyr temple,' said Jame, […] 'It may have been a lot smaller to look at than the one at Langadine, but it also seemed to be without a door, perhaps solid.' "