Keith Payne was born at Ingham, Queensland, on 30 August 1933. He attended Ingham State School and afterwards became an apprentice cabinet-maker. During this time he also served with the 31st Australian Infantry Battalion in the Citizens' Military Force. Seeking greater opportunities, Payne joined the Australian Regular Army in August 1951 and after his basic and initial employment training was posted to the 2nd Battalion, Royal Australian Regiment (2RAR) in December 1951.
Payne was transferred to the 1st Battalion, Royal Australian Regiment (1RAR) in July 1952 and later that month was sent to Japan as an infantry reinforcement. In September 1952 he was sent to Korea, where he joined his unit. He served with the battalion until they were rotated out of Korea in March 1953, whereupon he was taken on strength of Headquarters, 28th British Commonwealth Brigade. He remained with this formation until the end of the Korean War, and returned to Australia in August 1953.
In December 1954 Payne married Florence Plaw, a member of the Women's Royal Australian Army Corps. He was promoted to corporal the following year and spent much of the next five years attending various courses and schools of instruction to further his army career.
In February 1960 Payne was posted to the 3rd Battalion, Royal Australian Regiment (3RAR), then based at Enoggera in Queensland. He was promoted to sergeant in July 1961 and deployed to Malaysia in August 1963. During an operation on the Malay-Thai border in October 1964, Payne was slightly injured when he fell into a river as he was crossing. He remained on duty and returned to Australia with 3RAR in February 1965.
Later that month Payne was posted to the 5th Battalion, Royal Australian Regiment. However, the posting was only brief, and in June that year he was appointed as an instructor to the Officer Training Unit at Scheyville, New South Wales.
In February 1967 he joined the 2nd Pacific Islands Regiment in Papua New Guinea. He was promoted to warrant officer class 2 in May that year and returned to Brisbane at the conclusion of his posting in March 1968.
On 24 February 1969 he was appointed to the Australian Army Training Team in Vietnam. In May that year he was commanding the 212th Company of the 1st Mobile Strike Force Battalion when it was attacked by a strong North Vietnamese force. His company was isolated and, surrounded on three sides, Payne's Vietnamese troops began to fall back. Payne, by now wounded in the hands and arms and under heavy fire, covered the withdrawal before organising his troops into a defensive perimeter. He then spent three hours scouring the scene of the day's fight for isolated and wounded soldiers, all the while evading enemy troops, who kept up harassing fire. He found some 40 wounded men, brought some in himself and organised for the rescue of the others, leading the party back to base through enemy-dominated terrain. Years later, asked whether he was afraid, Payne replied, "My God yes, yes, I was." Payne's actions that night earned him the Victoria Cross.
He was evacuated to Brisbane in September suffering from an illness, receiving a warm reception at the Brisbane airport before entering hospital. He had recovered by November, and in January 1970 was posted as an instructor to the Royal Military College, Duntroon.
Payne received his VC from Her Majesty Queen Elizabeth II aboard the Royal Yacht, Britannia in Brisbane on 13 April 1970. He was made a Freeman of the city and of the shire in which his hometown was located. A park in Stafford, Brisbane, where Payne lived, was also named after him. He received the Distinguished Service Cross and the Silver Star from the United States, and the Republic of Vietnam awarded him the Cross of Gallantry with Bronze Star. He retired from the army in 1975, but saw further action as a captain with the Army of the Sultan of Oman during the Dhofar War.
Payne returned to Australia and became active in the veteran community, particularly in counseling sufferers of post-traumatic stress disorder.