A car cruises through the empty city streets of Poitiers, France in the dead of night. Inside two Interpol agents, Chase Devineaux and Julia Argent, are discussing an ongoing investigation into a series of heists across Shanghai, Cairo, and Switzerland. The only connecting thread is their suspect, a one "Carmen Sandiego", a woman who wears a distinctive red fedora and coat and appears at all the sites before the heist. Earlier in the day, that same red-coated woman was identified at a cafe in Poitiers, indicating a heist was set to happen somewhere in the vicinity.
Though they aren't sure where she will strike, fate intervenes and Julia spots Carmen ducking into an alleyway behind their car. Chase whips the vehicle around but only manages to catch up to her as she grapples to the rooftops. Not wanting to wait for backup, Chase pursues the woman in red on foot. Meanwhile, at the top of the building, Carmen looks out across the city skyline as she coordinates with her contact, a young man sitting at a computer named "Player". Her target appears to be the Cathedral of St. Pierre. The woman in red darts across the roofs as she approaches the cathedral before arriving at her mark. Connecting a small device to the electronic security system, her associate disables the system and Carmen sneaks in, though not without triggering a trap (that she evades with some hasty use of a nearby shield).
Chase Devineaux arrives on scene but is immediately slowed down by his choice to use the very slow elevator. Carmen uncovers a secret vault hidden behind a wall and Player helps decode the lock. However, upon laying eyes on her target, the "Eye of Vishnu", Carmen catches a glimpse of something that is even more important to her than the objective. At that moment, Chase (having run up the stairs instead of waiting for the elevator), demands entry into the room Carmen is standing in. After breaking in, he tries to apprehend Carmen but she gives him the slip, leading him on a pursuit across the rooftops of Poitiers. She comes to a stop above Chase's car before dropping down and sailing off on a portable hang glider. Chase, however, is not so lucky, loses his footing, and falls face first onto the hood of his car.
Chase, undeterred, orders Julia to manage the crime scene while he pursues Carmen in his car, whom he believes has fled to the train station. His hunch is correct, as Carmen lands at the next train stop and boards there. Chase arrives right as the train is leaving station, missing his window, and continues pursuing the train on the roadway. On the train, Carmen settles in but is immediately set upon by an unknown assailant who speaks with an Australian accent. Deploying a strange rod that can send out an EMP, he manages to disable all of Carmen's electronic equipment, leaving her out of communication with Player.
Carmen, however, is mostly soft-spoken with her attacker, speaking in a tone that implies familiarity. She identifies him as "Gray" and mentions that they both "passed Dr Bellum's class." Carmen tells him that she knew all along that what she had stolen was being tracked and did so deliberately in order to lure her pursuer to her. Gray remains unfazed and the two sit down opposite each other in the cabin, with Gray referring to Carmen by another name: "Black Sheep". The scene then flashes back to a younger Carmen who is sitting in the audience among other young people who are dressed like her. They are being addressed by a burly woman with green hair and a thick Texan accent, who says they are all cadets in the training academy for the "Valuable Imports, Lavish Exports" organization, or "V.I.L.E.", and introduces herself as "Coach Brunt".
Coach Brunt instructs the attendees to not contact the outside world and not to use anything but first names with one another until they are assigned code names. Gray, who is sitting in front of Carmen, snickers when she's addressed by Brunt as "Lambkins", which she takes as an insult and gives him a stern talking-to while demanding she be addressed as "Black Sheep". Back in the present, Gray expresses confusion over Carmen's transformation from a fellow cadet to who she is now. Wanting to know how she came to V.I.L.E. academy, he issues her an ultimatum: explain her entire past before the train reaches Paris.
Carmen begins by explaining she doesn't know exactly where she was born, only that she was told she was found alongside a road in Buenos Aires, Argentina as a baby. The only connection to her past were a set of Russian matryoshka dolls (nesting dolls) that were found with her. Whoever found her took her to a secret island that was also the site of the V.I.L.E. thieves academy. Through her childhood, various teachers gave Carmen a broad education of fundamentals such as reading and writing as well as cultural and geographic exposure. As she had been discovered without any sort of identification, Carmen was given the name "Black Sheep" by those raising her. Simply by being raised on an island that trained thieves, she became adept at the techniques practiced at V.I.L.E. academy on her own, despite being the youngest person on the island. Though she had a cheeky streak, she was mostly allowed to get away with whatever she wanted thanks to her guardians. After Coach Brunt bails her out of one of her pranks gone wrong, she absconds with a device that was on the person who she had wronged.
Because of the way she had been treated, Carmen had assumed she was saved as a baby by Coach Brunt, even though she could never be certain. Taking the device she stole from the man, she hid it in the largest nesting doll. Then, one night a few years later, the device she had stolen began to vibrate. She answers it and speaks to the person on the other end of the line; a boy who introduces himself as "Player". He explains he lives on the Canadian side of Niagara Falls and had managed to break through the encryption on the phone, which allowed him to place a call to it.
Inspired by making contact with the outside world for the first time, Black Sheep decides that it's time to see it for herself and volunteers herself as a V.I.L.E. academy cadet. She gathers the academy's lead faculty in order to state her case: Coach Brunt, Countess Cleo, Dr. Bellum, Shadow-san, and the faculty's headmaster, Professor Maelstrom. Acknowledging that her age would normally put her beneath consideration, Black Sheep argues that she still has more than enough background to be a candidate for acceptance. The faculty are somewhat skeptical but also recognize that her upbringing does indeed give her the sort of talents that are sought after in V.I.L.E. graduates. Shadow-san is the most outspoken member and is highly unconvinced that Black Sheep has the qualifications for a professional thief. Black Sheep remains resolute that her future lies with V.I.L.E. academy, prompting a vote from the other faculty members. The council outvotes Shadow-san at a ratio of 4:1, granting Black Sheep full admission to the academy.
Black Sheep moves into the dorms of V.I.L.E. academy and meets four other students: Antonio, Jean-Paul, Sheena, and Graham/Gray himself. Immediately after meeting Black Sheep, Sheena begins harassing her but Gray steps and settles things in the interest of order between roommates. While socializing with Gray in the halls, Gray explains he had been a junior electrician at the world-famous Sydney Opera House until he realized he could use his skills for burglary, which is how he caught V.I.L.E.'s attention. The two form a strong friendship through their various courses at V.I.L.E. academy. Black Sheep begins formally cultivating talents in thievery, combat, identification of rare items, gadgetry, and deception with the help of the instructors at the academy.
Despite now being a cadet, Black Sheep's tendencies don't go away and she continues to pull pranks, her usual favorite being water-ballooning V.I.L.E.'s bookkeeper on her annual trip to the island to deliver a secure hard drive containing information V.I.L.E. uses to plan future operations for the coming year. After roping in her fellow dorm mates into the prank, they're caught and brought before the faculty for discipline. As before, Shadow-san is particularly displeased and demands that Black Sheep face expulsion for her actions. Gray steps forward and says the entire group is responsible, against Sheena's protests, and the five are sentenced to detention.
Making the best of their situation, Gray suggests they pitch code names to adopt. After a round of unsuccessful suggestions, Gray combines his first name with the world "crackle" to create "Graham Crackle", which he shortens to "Crackle" after the other students talk him out of it. Jean-Paul goes with "Le Chevre" (French for "the goat") because of his affinity for coming in from above. Antonio adopts "El Topo" (Spanish for "the mole") due to his use of drill claws that allow him to approach from below. Sheena takes "Tigress" due to her sharp claw-gloves and optical hardware that lets her see as well as a cat in the dark. Finally there is the class mime, who takes the name "Mime Bomb".
Graduation approaches and the only thing that remains is for Black Sheep to pass her final exam. Shadow-san's final exam, a pickpocketing exercise, is passed by Tigress taking advantage of her claws and optics to rip open Shadow-san's pocket to steal the target. Then Black Sheep tries but discovers she is unable to successfully pickpocket her instructor. The results for the exams come in and everyone from Black Sheep's dorm graduates...except for Black Sheep herself. Black Sheep confronts Shadow-san and demands a second opportunity, accusing him of rigging the exam against her by not having the objective on his person at all, but is refused and told to study for another attempt in a year.
Frustrated with the situation, Black Sheep decides that if she can't graduate, she'll simply join a mission by herself. She sneaks out one night and boards the chopper taking the other graduates to their first caper. However her escape was not unnoticed...
