Nadja est née en 1955 à Alexandrie en Égypte, d'une mère peintre de parents russes et d'un père médecin d'origine libanaise. Son enfance au Liban et en région parisienne n'a rien d'ordinaire : pas d'école mais des cours par correspondance jusqu'à l'âge de treize ans, et surtout des histoires racontées et dessinées par sa mère Olga Lecaye.  En 1989, avec Chien bleu, un album aux gouaches fauves, Nadja obtient le prix Totem du Salon du livre de jeunesse de Montreuil. C'est l'entrée de la peinture dans l'album. Bien d'autres albums suivront, empreints d'un style expressionniste qui s'exprime avec force dans des peintures pleine page.
Poursuivant la complicité créatrice initiée dans l'enfance avec les siens, elle aime faire des livres avec son fils, Raphaël Fejtö, sa mère Olga Lecaye et son frère Grégoire Solotareff. Avec ce dernier, elle a concocté des parodies de contes célèbres. C'est une autre facette de son talent qui apparaît alors, pleine d'humour et d'irrévérence. Dans cette même veine, elle a signé la célèbre série des Momo, celle désopilante et théâtrale des Petite princesse et d'autres pastiches de contes.
Pour les grands, elle a créé des romans graphiques, notamment, L'homme de mes rêves (Cornelius), Les filles de Montparnasse (Olivius), Ô Cruelle (Actes Sud).
Elle vit à Paris où elle partage son temps entre peinture et illustration.