Камелія Тодорова народилася 21 січня1954 року в Софії. В дитинстві займалася художньою гімнастикою та балетом. У 1976 році Тодорова закінчила Болгарську державну консерваторію. Камелія почала брати участь у вокальних конкурсах, а в 1980 році вийшов перший альбом співачки «Софийски диксиленд и Камелия Тодорова». Паралельно зі співацькою кар'єрою Тодорова також брала участь у телевізійних та кінематографічних проєктах. Другий альбом Камелії «2 Souls in 1» вийшов у 1991 році. Поступово Тодорова стала однією з найпопулярніших співачок Болгарії.