She was born in Toronto, Ontario, Canada, the first child of her parents, Promod and Chitralekha Patnaik; she is seven years older than her sibling Devraj Patnaik. Her parents were born in the state of Orissa (now Odisha), India, and emigrated to Canada in the 1960s. Patnaik made numerous trips to India with her family in her youth.
Patnaik first and primary dance guru was her mother, who began training her as an Odissi dancer from a very young age. She has also received training from such notables as (late) Padmashri Pankaj Charan Das, (late) Padmabibhusan Kelucharan Mohapatra, Padmashri Sanjukta Panigrahi and Padmashri Gangadhar Pradhan.