Kya: Dark Lineage begins with Kya, the protagonist, and her half-brother Frank home alone. Kya hears a suspicious noise and follows it downstairs to finds Frank in a previously unknown room in the basement. Frank finds a secret room in their house. When he places a medallion he finds in the secret room onto an altar, a portal appears taking Kya and Frank into it.
Once Kya awakes she sees three strange yellow/orange creatures staring at her. Before she could ask where she was and what was happening the creature said that she had to start running right away so she wouldn't get captured by other creatures that were chasing them. Soon all the creatures are captured except one, and after Kya and the creature reached a safer area, the creature tells Kya that his name is Aton, Aton brings Kya to a secret entrance to his village called Nativ City, then Kya asks Aton what the thing was that was chasing them. Aton tells Kya that the creatures that were chasing them are called Wolfen, after which Kya and Aton enter Nativ City. Aton brings Kya to Atea, a wise Nativ, who tells Kya that Wolfen are Nativs that were transformed by Brazul, who happens to be Kya's father.
Kya tells Atea that she wants to find her brother Frank, and Atea introduces Akasa, a Nativ that is an expert at fighting. Akasa gives Kya a magic bracelet that allows her to use fighting moves like a salto kick or a plain kick. Kya tells Atea that she will help rescue the Nativs that have been turned into Wolfen while she searches for her brother.
Kya: The playable heroine of the story who was sucked into the Nativs' world, along with her half-brother Frank. Kya is a strong and independent young woman who engages on a quest to find Frank. By attempting to do this, she is also helping the Nativs to stop the evil Brazul's plans. In turn, she is adored by them and they will be of support when necessary. Kya has a deep hatred for her father, because she believes he simply abandoned her when she was younger.
Frank: He is Kya's half-brother. When they were transported into the world where the story takes place, Frank landed on a completely different location, and he was almost immediately captured by Wolfen, who brought him to Brazul's lair. He spends most of the game trapped in there.
Brazul: This fearsome presence is the monarch of this parallel world, and the very creator of the dreaded Wolfen. He possesses vast knowledge about dark magic and has conquered most of this world by capturing Nativs and turning them into Wolfen. Very early in the game, he is revealed to be Kya's real father.
Nativs: They are the friendly tribe that is being hunted and transformed by Brazul. They live in the secluded Nativ City, which is their secret haven from Brazul's forces. Nativs resemble furry animals with a slightly canine appearance. Most of them sell helpful items to Kya, and as she frees more Nativs, more stores open up.
Some of the Nativs play an important role in the story:
- Atea: He is the wisest (and probably oldest) of the Nativs, therefore assuming his position as their great elder. Atea sympathizes with Kya from the start, and he tells her that she isn't the first of her kind to step into their world (referring to Brazul). He advises Kya throughout her quest and tells her about his world, and how she can get back to her own. Additionally, he gives Kya the power of exorcizing the Wolfen. He has a nameless pet bird that sits on his cane all the time, which Atea bangs against the ground when he starts getting annoying.
- Aton: Aton is the strongest of the Nativs. He is the one who saves Kya in the beginning of the game, guiding her into the Nativ City. However, he doesn't trust her too much, and once the other Nativs start idolizing Kya, he slowly starts developing a certain jealousy. he is also Area's best friend.
- Akasa: The combat teacher who runs a dojo in Nativ City. He teaches Kya various techniques on how to fight the Wolfen.
- Area: Area is a normal nativ that has a liking for surfing, he is quite a coward, Atea was captured because he was so cowardly, he's always talking about kya's mission. he also knows how to drive ships. Aton's best friend.
- Amera owner of a shop where kya can buy fruit.
- The Snore An unseen nativ that is told to be so boring that kya should not talk to him.
Wolfen: The Wolfen are the creatures under Brazul's orders. Originally Nativs, they were transformed by Brazul and sent out there to capture the remaining people from their tribe. Wolfen, as their name more-or-less implies, are creatures who have the physical appearance of anthropomorphic wolves. Kya is the only person who can fight the Wolfen and return them back to their Nativ forms.
The Roots: Is a jungle where kya crashes down and is found by Aton.
Nativ City: The nativ's secret city where kya can buy stuff, practice moves and play minigames.
The Flying Forest: Is a forest that contains the medalion that kya needs to equip runes, it also has an energy bar and a way to The Hunters Domain.
The Hunters Domain: An island where a wolfen/wolfun called the hunter( who is a wolfen/wolfun himself) is the boss of the hunter's domain. Kya goes there to save Atea.
The Quarry: Is a mountainous place where kya goes to find the cannon to the forgotten island.
The Air Post: Is a rocky world, that contains the old cannon to the forgotten island.
The Forgotten Island:An island full of lava where kya finds Frank/Franck.
Wolfen/Wolfun City:Wolfen/Wolfun city is where the wolfun live.
The Fortress: The Fortress is brazul's rocky lair, here is where kya fullfills here quest.
Dogs: Purple dogs tha can jump out at kya and eat her.
Spiders: Spiders are small blue spiders that climb on walls, there is a bigger version that shoots strange blue stuff at kya to hurt her.
Shooters Are purple creatures that resemble a mix between a bull dog and a spider and shoot a strange ice blast.
Micken: round red animals that love fruit and would do anything for it. Kya is able to jump on them and use them as a soccer ball.
Shocker: Are blue oval creatures that shoot electricity at kya.
- After you reach Nativ Village for the first time, Atea tells you to go buy a weapon. In the cutscene, Kya already has the Basic Boomy, although she has not purchased it yet. Once the gameplay begins, the boomy disappears.
- When Kya buys her silver bracelet in nativ city it is black inside the shop until she buys it.
- While Atea is captured by Wolfun/Wolfen you can still see him walking around the city.
- The game was originally to have a sequel, but due to the poor ratings, the idea was scrapped. Eden Games actually began production of a sequel, or at least started plans to do so according to an interview in which someone from the developer (Eden Games) or publisher (Atari) explicitly stated "We were going to make a sequel, but the game had bad sales so we decided not to do so." While the ending of the game leaves it open to a sequel, it's just as likely that Atari asked Eden Games to keep the ending open for a sequel in case the game became a smash hit.
- Kya is the only known female in the entire game, although it is unsure if the Nativs have two genders, or if any of the Nativs in the streets of Nativ city are female. It could perhaps be stated that Kya is the only significant female character.
- There are 260 Wolfen that Kya can turn back into Nativs but you only meet around 20 (or fewer) Nativs in Nativ City, in the entire game.
- In the anime Naruto, the character called Tenten is a weapons expert. In episode 43, Tenten takes out a scroll full of weapons and shoots an array of different weapons at an enemy. Two of the weapons resemble Kya's boomy, except they were both metal and one did not have a handle, even though she does in fact throw two weapons similar to Kya's boomy it is just coincidence. The insane number of weapons Tenten uses (as well as the variety of them) means that the weapons mentioned couldn't possibly be like that on purpose. Additionally, the release schedule makes it likely that it's just random coincidence.