While the alien race we know as the Klingons appeared in the original Star Trek TV series, they only achieved the iconic look and used their own language in the first Star Trek feature film in 1979. The language they spoke in Star Trek: The Motion Picture consisted of words made up by James Doohan, who played Engineer Scott. The role of non-human species and their languages would expand for further movies. About that time time, Marc Okrand of the National Captioning Institute was preparing to do close-captioning in real time for the 1982 Academy Awards.
During preparations in L.A., Okrand was having lunch with an old friend when serendipity struck. The friend was working on what would become Star Trek II: The Wrath of Khan, and the film just so happened to need a linguist to dub a conversation between Vulcans Spock and Saavik (played by a young Kirstie Alley). Using clues from the little bit of Vulcan spoken in the first film, Okrand got to work. But Vulcan at this time wasn't really a language. "The scene was filmed with the actors speaking English. My job was to make up gobbly-goop that fit the lip movements and then was dubbed in," Okrand says. Two years later, he was asked backed to work on the third Star Trek movie, but this time the task was a bit more complex: to develop the Klingon language.
Okrand started with the scraps of words the Klingons had already used, and built an entire language from the bottom up. He tells a little of how he did it at Popular Mechanics.