Mary Galster Layton Starkey was born 26 October, 1949, in Buffalo, New York. Influenced by the stories of her father's service in World War II as well as the boys in her high school going off to fight in the Vietnam War, she wanted to be a U.S. Army Nurse. In 1968, she took the Armed Services Vocational Aptitude Battery test and was recruited for her high-test scores.

Starkey joined the Women’s Army Corps (WAC) in 1968 and did basic training at Fort McClellan in Alabama and then medical training at Fort Sam in Texas. She was then sent to work in Walter Reed at the National Military Medical Center in Washington D.C where she worked as a medic with obstetrician doctors in 1969. Shortly after Starkey then got pregnant and was discharged from the military.

In 1975, Starkey re-joined the military after both of her children had died. She did her basic training at Fort McClellan before being transferred to Fort Jackson in South Carolina, where she was at cook school. She was then sent to Fort Bragg where she went to jump school and learned about airborne training and how to jump out of planes.

After her training Starkey went to Korea from 1978-1979 as a cook with her unit. She was one of the only women in her mess hall and won the Connelly Award for Excellence in Army Food. She was then sent back to Fort Bragg where she worked with both men and women in the mess hall. Starkey stayed at Fort Bragg until she was discharged due to a broken leg in 1983.