Pouco depois da Revolução Russa de 1917, a mãe de Toumanova, Eugenia Toumanova, deixou a Geórgia, Rússia, à procura de seu primeiro marido, Konstantin Zakharov. Ela estava grávida na época. Ela deu à luz Toumanova na Sibéria. Foi verificado que Toumanova é de ascendência georgiana.
Os pais da Toumanova se separaram durante a revolução. Toumanova tinha 18 meses de idade antes de seus pais serem encontrados um ao outro. A família foi da Rússia para Xangai, China. Eles viveram lá por um ano. Depois se mudaram para o Cairo. Depois de morar em campos de refugiados, a família se mudou para Paris. Havia lá uma grande comunidade de emigrantes russos.
Depois de se mudar para Paris, Toumanova recebeu aulas de piano e estudou balé com Olga Preobrajenska. Toumanova disse que ela foi sua "primeira e única professora permanente" e uma "amiga imortal". Ela estreou na Ópera de Paris aos dez anos de idade no balé infantil L'Éventail de Jeanne. George Balanchine a viu na aula de ballet e a contratou para o Ballet Russe de Monte Carlo de Basil como uma das três "baby ballerinas".