Historical information provided by The Jim Henson Company Archivist:
By the mid-1980s, Muppet fever was running high with the releases of The Great Muppet Caper and The Muppets Take Manhattan. Between the releases of the Muppet films, the Muppet art exhibit, and the Fraggle Rock premiere, ideas for Labyrinth were being tossed around. From 1983 to 1985 over twenty-five treatments and scripts were drafted and revised. It was important to Jim to make a film that had characters the audience could relate to, and the role of Sarah was essential in accomplishing this. Her character was constantly being tweaked to create a leading role that was intelligent, sympathetic, and likeable. But it was crucial for her to also have flaws. Upon reading a rewrite from June of 1984, Terry Jones had this to say about reworking Sarah, “I don’t think we need to lay Sarah’s character on the line too much. The function of the late-for-baby-sitting episode is to establish her thoughtlessness and refusal to grow up and accept responsibility, but we’ve got a live actress playing the part and she can convey a lot of this in her manner and by the way she talks and walks.” In 1985, Elaine May was brought in to polish the script. The changes she made in humanizing the characters so pleased Jim that shooting began using her material.
The search for an actress to play Sarah was a long and tedious one. Many might be surprised to learn who tried out for the role of Sarah. Auditions started in the U.K. in April of 1984. On July 5th a “dark and cynical” Helena Bonham Carter auditioned along with nineteen other actresses. Bonham Carter was listed as a potential candidate, but it was thought best to have Sarah be played by an American actress. Monthly auditions were held in the U.S. until January 29, 1985. Jane Krakowski, Yasmine Bleeth, Sarah Jessica Parker, Mary Stewart Masterson, Laura Dern, Maddie Corman, Kerri Green, Lili Taylor, Laura San Giacomo, Ally Sheedy, and Mia Sara all auditioned for Jim. Jane Krakowski, Ally Sheedy, and Maddie Corman all gave good readings and were top candidates for the role of Sarah, but Jennifer Connelly won Jim over. Connelly moved to London in February, rehearsals began in March, and shooting started on April 15th. Despite her youth, her professionalism showed on set, as well as in her performance. She shared a strong rapport with Jim during shooting and her friendship with Jim continued after the film was completed. It wasn’t a complete loss for many of the actresses who auditioned for Sarah. Several ended up being included in various Henson-affiliated projects: Mia Sara as Ondine in Jack and the Beanstalk: The Real Story, Sarah Jessica Parker on Sesame Street, and Jane Krakowski in A Muppet Christmas: Letters to Santa.