Okeh was founded by Otto Heinemann (1877-1965), a German-American manager for the U.S. branch of German owned Odeon Records. As World War I raged in Europe, Heinemann thought it best to have an American based company. He incorporated the Otto Heinemann Phonograph Corporation in 1916, set up his own recording studio and disc record pressing plant in New York City, and introduced the company's line of records for public sale in September of 1918. Heinemann formed the name of the record label "Okeh", from his initials; early disc labels rendered the name as OkeH. The first discs were vertical cut. In 1919 Okeh switched to the lateral cut method of sound recording, more usual for disc records. That same year the name of the label's owning company was changed to the General Phonograph Corporation. The name on the labels was changed to OKeh. The common 10 inch discs retailed for 75 cents each; the 12 inch discs for $1.25. The company's musical director was Fred Hager, who also appeared under the pseudonym of "Milo Rega" (Hager's middle name and his surname recersed).
Okeh began by issueing popular songs, dance numbers, and vaudeville skits similar to the fare of other labels, but Heineman also wished to experiment with music for audiences neglected by the larger record companies. Okeh produced lines of recordings in German, Czech, Polish, Swedish, and Yiddish for the USA's immigrant communities. Some were pressed from masters leased from European lables, others were recorded by Okeh in New York.
In 1920 recordings by African-American blues singer Mamie Smith were a surprise smash hit for Okeh. The company perceived the significant little tapped market for blues and jazz by African American artists. In 1922 Okeh hired Clarence Williams to act as director of "Race" (African American) recordings for Okeh's New York studios, in addition to making recordings under his own name. Okeh then opened a recording studio in Chicago, Illinois, the center of jazz in the 1920s, where Richard M. Jones served as "Race" recordings director. Many classic jazz performances by the likes of King Oliver, Sidney Bechet, and Louis Armstrong were recorded by Okeh.
Okeh Records pioneered the practice of "location recording" in 1922. Starting in 1924 Okeh also sent mobile recording trucks to tour other parts of the country to record performers not heard in New York or Chicago. Regular return trips were made once or twice a year to New Orleans, Louisiana, Atlanta, Georgia, San Antonio, Texas, Saint Louis, Missouri, Kansas City, Missouri, and Detroit, Michigan, recording a wealth of jazz and early country music artists.
In 1926 Okeh switched to the electric microphone system of audio recording. On November 11 of that year, controlling interest in Okeh was purchased by Columbia Records. The Okeh label was continued until 1935. Columbia again revived the label in 1940 after they lost the rights to the Vocalion name (by dropping the Brunswick label) and pressed it until 1946; it was revived in the 1950's and used sporadically, and in the 1990s.