Willie is first mentioned in the comic as Cat R. Waul gives a speech saying that in Green River young girls are free to find love. Tanya day dreams about him while saying his name, and Fievel laughs at her. He was never mentioned before this point. Later on, Tanya tells Miss Kitty that she used to have a crush on a boy in New York who worked as a cheese vendor. And at the very end of the comic when everyone is celebrating Waul's defeat, Tanya sees Willie, who has just moved to Green River, and though he doesn't recognize her at first he runs into her arms when he realizes its Tanya.
Several plot points in Fievel Goes West, such as the lyrics to Dreams to Dream and parts where Tanya seems to be pining for love hint that Willie was originally supposed to be in the film but got cut. More evidence comes from Tanya's An American Tail trading card, which states that she "has love for a certain young mouse". It would be odd if it were referring to Fievel.
Possible Film Appearance
Willie may actually have made it into the film briefly; Tanya accidentally presses noses together with a young mouse who bears resemblance to Willie when the town celebrates Waul's defeat. Though presented as just a random mouse, it's very possible that this mouse was to be Willie before his character got cut from the script. His clothing is very similar to how Willie is pictured in the comic.