Kelia Streshinskaia was born in 1915 in Petrograd (subsequently named Leningrad; present-day St. Petersburg, Russia), as the only child of her parents. Her father was a photographer. The family was poor, and, after finishing seven classes of school, Kelia started working at a factory. In 1934, she entered the newly created Department of Semitic Studies of Leningrad University, studying at its Hebrew section. In 1938, with great difficulty (Kelia had poor linguistic abilities), she graduated from the University and submitted her application for postgraduate studies at the Department of Art History. She began to work at the State Hermitage Museum.
In June 1941, the Soviet-German war broke out, and Kelia's first task was preparing the collections of the Hermitage for evacuation. When the first train with the Hermitage exhibits had left the city, Streshinskaia – who was 170 centimeters (5 feet 7 inches) tall, handsome, and strong – volunteered for the Red Army as a military nurse. In mid-October 1941, she began to work in this capacity at military hospitals, first in Leningrad, and then – from January 1942 on – in the surrounding area and on the Baltic coast (west of the city), where she was issued a military uniform for the first time. In addition to performing the regular duties of a nurse, Streshinskaia, like her colleagues, also had to clean the hospital and procure firewood for it. During the warm season, she had to cultivate the vegetable plot that provided food for patients and staff alike.
In January 1944, during the battle to lift the German siege of Leningrad, Streshinskaia and some other medical workers from her hospital were transferred to the frontline. Here, at frontline hospitals, she had to work 36-hour shifts, with several hours of sleep before the next such shift. After that, she was awarded the medal "For the Defense of Leningrad" and promoted to the rank of major sergeant (starshina). In 1944, Streshinskaia, as a nurse, participated in the Red Army offensive south of Leningrad, and later served in Estonia, Poland, and northeastern Germany.
Kelia's parents died during the Siege of Leningrad.
After the war, Kelia Streshinskaia continued to live in her native city.