After Miss Clavel feels better, a letter is delivered to the house, saying Madeline's long-lost Uncle Horst from Vienna is coming for a visit. Ecstatic that she still has a family, Madeline eagerly awaits his arrival. Uncle Horst arrives later in the week, and is reacquainted with his niece, whom he remembers fondly. Madeline is pleased to meet him, and Horst presents all twelve girls with lace collars as a gift. Uncle Horst then announces that he has been made Madeline's new legal guardian, and that she is to accompany him to his hometown of Vienna, where she can attend a fine finishing school. Although nobody wants her to leave, Madeline reluctantly agrees to go.
That evening, Uncle Horst returns to dine with the girls, as well as Lord Cucuface and Pepito's family. At dinner, Horst tells of the Austrian School to the girls, certain that it will be more fulfilling than Madeline's current school. The girls, wanting to prove that their home is just as good, puts on a musical to display their talents to Uncle Horst. Horst, however, does not sway from his intent and informs Madeline that they leave the next morning, while assuring her that she will come to love Vienna. Uncle Horst leaves for his hotel that night, during which Lord Cucuface reminds him of Madeline's inheritance, which Horst says he will be responsible for.The night before Madeline was to leave with her uncle, Pepito tried and failed to stop the sun from waking up by preventing the rooster from doing his morning crowing. Soon, Madeline leaves with her uncle for Gare de l'Est where the Orient Express will take them to Vienna. Before leaving, Miss Clavel gives Madeline her mother's beaded necklace, which she was to give Madeline "at the right time". The two then depart for Vienna. However, the man thought to be Madeline's uncle instead took her on the Paris Métro and to an unfamiliar part of town, even abandoning her pet dog Genevieve on the way. Fearing that she is being kidnapped, Madeline throws pieces of her necklace down to make a trail to where she is taken to. Madeline is soon taken to a lace store run by Madame LaCroque, where Uncle Horst accidentally reveals that he is French, not Viennese German as he had claimed. It is then revealed that Horst isn't her uncle at all, but a man named Henri, a failed Shakespearean actor. Inside are girls who were also kidnapped and were forced into making laces to sell. One of the girls, Fifi, befriended Madeline.
Shortly after Madeline left, Miss Clavel, the girls, and Pepito tried to stop her and Horst so that Pepito could give her his parting gift: A shrunken head from Brazil. They arrive at the train station, only to learn that the two had taken the Métro, not the Orient Express. They also find Genevieve abandoned at the station. Fearing the worst, Miss Clavel enlists the police to help them rescue Madeline.
Meanwhile, at the lace shop, Fifi's cough turns one of LaCroque's laces yellow. LaCroque banned her from using white lace, and must instead make black lace. Madeline tries to defend her, but she ends up being thrown into the detention room. Fifi tells Madeline of how LaCroque was once a cabaret dancer who had once torn her dress and fell off the stage when performing. In total humiliation, she refused to perform, and sold her long hair to make lace. She then went into the lace business and kidnapped all of the girls to work as her miserable servants.
Meanwhile, Pepito and Madeline's friends go off to find her on their own and discover the trail of beads that led to the lace store. A customer claims to LaCroque she wants red lace, which gives her the idea to cut off some of Madeline's hair.Madeline tells her new friends when an escape plan fails that they may be small, but can follow as one. LaCroque interrupts and cuts off some of Madeline's hair, while Pepeto is able to swipe off LaCroque's wig while outside the window. Miss Clavel and the police were able to discover and catch the so-called uncle after a boy trips him after refusing to give any change.
While Madeline is still in the lace factory, Pepito and the girls use the shrunken head to first knock off La Croque's wig, and then frighten her to the ground. Meanwhile, Miss Clavel is able to convince Henri to lead them to Madeline by telling him " Surely, if you help, the cops won't be so hard on you." Henri reluctantly agrees to lead them there.
Madeline and all of her friends are able to tangle LaCroque in lace just as the police car pulls up. Henri, feeling guilty, tries to escape, only to be tripped by Pepito's lace trick, allowing the girls to tangle him up as well. LaCroque accidentally kicks Henri during the chase, just before he trips. She and Henri are arrested by the police and taken to jail. The other factory girls still have no place for home. Madeline has a great plan, though.
That night, Madeline tells her friends that they can do with their reward money. Danielle will go shopping for fashion, clothes and jewelry, Chloe will travel to exotic countries around the world, and Nicole will own a zoo.
Madeline receives a huge reward after returning home because of her work, and used it to open a school for the orphaned girls and realize that she has family all around her. All of the girls from both schools rejoice in the fact that they are all truly a happy family.