McKenzie was born in a tipi, and baptised in the Washita River. He was educated at the Rainy Mountain Kiowa Boarding School where it was mandatory to speak the English Language; those who used the Kiowa language were threatened with physical punishment. Afterwards, he attended the Phoenix Indian School, Union High School, Lamson College, and Oklahoma State University.
McKenzie attended the Phoenix Indian School with Nettie Odlety (ca. 1896–1978), whom he married on 23 August 1919. At school the couple wrote each other letters in Kiowa. They also were some of the earliest Kiowa photographers, taking photographs in Arizona in 1916.
When in 1918 the Smithsonian Institution sent the anthropologist John Peabody Harrington to Oklahoma to study the language of the Kiowa, McKenzie was his translator. This began a decades-long scientific examination and recording of the Kiowa language which until then had been purely an oral language. They jointly developed a valid phonetic alphabet, which also resulted in the publication of Vocabulary of the Kiowa Language (1928) and Popular Account of the Kiowa Indian Language (1948), in a collaboration that extended into the 1950s. All this time, from the 1920s-1950s, McKenzie - never an academic - was a stenographer in the Indians Monies Section of the Bureau of Indian Affairs.
Late in his life, in close cooperation with Laurel Watkins, McKenzie published A Grammar of Kiowa 1984. Some compared his work with the development of the Sequoyah and Cherokee alphabets. He also translated many texts from English, including Baptist hymns.
His contributions to the Kiowa were honoured by the University of Colorado in 1991 with the awarding of an honorary doctorate, and his 100th birthday was honoured with a ceremony in the Red Buffalo Hall of the Kiowa Tribal Complex in Carnegie, Oklahoma. McKenzie was a Freemason.
Nettie and Parker had two daughters, Esther Hayes of Mountain View and Kathryn Collier of Wewoka. They also had three sons, William, Henry, and Robert, all deceased.