She is voiced by Jill Talley.
She is first mentioned in "Memory of a Memory" by Ash when he reveals to Marceline that he sold her teddy bear, Hambo to her so he can get enough money to buy a new wand. This cuses Marceline to break up with him.
She made her official debut in the episode "Sky Witch" when Marceline tracks her down and asks Princess Bubblegum to help inflitrate her lair and get back Hambo. Maja send her Crabbit Familiar to attack them and after getting to her castle PB confronts Maja and makes a trade with her for Hambo. After Marceline and Bubblegum leave, it's revealed that Bubblegum traded her night shirt to Maja for Hambo. Maja states that the sentimental value of the shirt was far greater then the sentimental value for Hambo. She states that she's cooking up something big while repeatedly attacking her Crabbit Familiar.
She reapaeras in "Something Big" where she uses the sentimental value of Princess Bubblegum's shirt to awaken Darren the Ancient Sleeper. She and Darren then attack the Candy Kingdom, but are stopped by Finn and Jake using the Ancient Psychic Tandem War Elephant. After Darren is destroyed, Maja gets knocked out from the impact landing. She is later cared for by the Ancient Psychic Tandem War Elephant.
Maja appears in a flashback by Cherry Cream Soda Girl in "Cherry Cream Soda" attacking the Candy Kingdom with Darren and in the process killing Cherry Cream soda Girl's husband Root Bear Guy. Maja then appears in "Flue Spell" during Jake's outing montage. She is still knocked out and with Ancient Psychic Tandem War Elephant.