Maja (full title: Maja the Sky Witch) is a character who first appears in "Sky Witch." She buys Hambo from Ash and later trades Princess Bubblegum Hambo in exchange for Princess Bubblegum's rock t-shirt. She uses the material's emotional essence for a brew, which she says "will be big." Her companion is the Crabbit Familiar, whom she abuses. She has the ability to hover and can shoot bolts of electricity from her hands.
Maja has pea-green skin and brown hair tied into a large bun that is almost the same size as her head. She wears a light-brown cape covering what seems to be a teal dress or Japanese kimono with tight sleeves. Her voice has a magical, reverberating effect to her words. In "Something Big," while she still maintains her cape, she wears a cutoff version of Princess Bubblegum's rock shirt and a green skirt, her eyes are also appear bigger than they did in "Sky Witch".
Due to her ability to obtain energy from feelings of others, Maja is willing to do anything and destroy anyone in her search for power. This is seen in "Something Big," where she raises the ancient war-creature Darren to attack the Candy Kingdom. Her invasion leads to the deaths of Root Beer Guy and a number of candy soldiers. Even after losing the battle and entering a comatose state, Maja can only think about completing her original plan. This is seen when she tries to convince the Ancient Psychic Tandem War Elephant to attack the Candy Kingdom while it tries to help her.
She does not seem to think very highly of anyone but herself. She calls Ash a "wenis," Marceline a "tranch," and Princess Bubblegum both a "bozo" and a "tranch." Maja dislikes the notion of friendship as she is disgusted by the Ancient Psychic Tadem War Elephant's efforts to befriend and assist Maja in her time of need. In addition to this, she appears to have sadistic tendencies—she derives pleasure from zapping her Crabbit Familiar with her magic.
- "Memory of a Memory" (indirect)