Deja was born on April 1, 1957 in Gdańsk, Poland, but moved with his family to Dinslaken, Germany, in 1958. He credits seeing Disney's The Jungle Book as an 11-year-old with inspiring him to become an animator. After graduating from Theodor-Heuss Gymnasium (secondary school), he studied graphic design at the Folkwang Hochschule in Essen, Germany.
A lifelong fan of Disney animated films, Deja was hired by the studio in 1980 after he had corresponded with Eric Larson, one of Disney's senior Nine Old Men of animation who ran the studio's training department. The first film on which he worked was The Black Cauldron, during which time he shared a cubicle with future film director Tim Burton.
During his rookie days at Disney, Deja sought mentorship and practical advice from seven of the then-living Nine Old Men, who were already retired before his tenure. Deja has collected information on the Nine Old Men over the years, and has stated that one of his ambitions is to publish one book for each of the Nine Old Men.
Deja is best known as the supervising animator of some of the most memorable Disney villains: Gaston from Beauty and the Beast, Jafar in Aladdin and Scar from The Lion King. He also animated Roger Rabbit from Who Framed Roger Rabbit, King Triton from The Little Mermaid, the titular character from Hercules, Lilo from Lilo & Stitch, Queen Narissa from Enchanted, Mama Odie in The Princess and the Frog, and Tigger in Winnie the Pooh. In addition, he is the current resident specialist for the animation of Mickey Mouse.
In 2006, at the 35th Annie Awards, Deja was awarded the Winsor McCay Award for outstanding contribution to the art of animation. Recently, he began a blog where he shares some of his collection of the work of the early Disney animators.
Deja is openly gay. His sexuality has been discussed as an influence on the development of some Disney characters.