Upon Fry's initial arrival in the future, he shows a physical interest in Leela. This is quickly squashed when she turns to face him, revealing her eye. Later in the episode, Fry and Leela begin to form an emotional connection, as both are entirely alone in the universe. In "My Three Suns", it is shown that although Fry routinely rejects her advice, landing him in a great deal of trouble, he ultimately cares for her, as evidenced by the fact that the thought of Leela dying was the key to make him cry out the Trisolian emperor.
It can be debated whether the initial beginnings of the actual relationship started in "Space Pilot 3000" or "A Flight to Remember", but there is certainly a difference; in the first episode, Fry is immediately interested in Leela, while in the latter episode, Fry and Leela almost kiss for the first time, which may indeed have sparked Leela as a love interest for Fry.
In "Xmas Story" Fry risks his life to buy Leela a present, and they seem to form a stronger emotional connection.
Not much mention is made of Fry's interest in Leela during the second season. Hints at Fry's continued affection mainly focus around the jealousy he shows towards other men in Leela's life, such as Alcazar.
Leela has been quoted as saying that she loves Fry's boyish charm, but hates his childishness.
The one-sided quest
In "Parasites Lost", Leela begins to fall for Fry's new intelligent and capable personality, but this proves to be the work of the worms inside Fry. After the worms leave, Fry reverts to his awkward self, and Leela immediately loses interest in him.
In "The Cyber House Rules", Fry is the only member of the Planet Express crew who believes Leela is beautiful as she is, and doesn't need phaser eye surgery to make her fit in with "average" people.
Once, in "Time Keeps on Slippin'", Fry manages to get Leela to marry him. Unfortunately, due to time skips, no one has any memory of what he did to make Leela love him. Leela believes Fry tricked her into marrying him, and before anyone can prove otherwise, another time skip leaves them divorced. Later, Fry realizes that he had pushed stars to spell out "I love you, Leela" and that is how he got her to love him. That message is soon imploded before Leela sees.
In the episode, "Love and Rocket", Fry saves Leela's life on Valentine's Day when her portable oxygen tank runs out during a desperate attempt to halt the insane autopilot of the Planet Express Ship. Leela then saves his life by giving CPR. Fry and Leela appear to grow closer, and may have even shared a romantic moment together on the balcony of Planet Express, if only Dr. Zoidberg hadn't interrupted them.
In "Teenage Mutant Leela's Hurdles", teenage Leela and Fry go on a date.
Fry once again puts Leela's safety before his own in the episode "The Why of Fry". When Fry travels back to the year 1999 to stop Nibbler from freezing him, Nibbler asks Fry, "Is there nothing in the future worth saving [from the brainspawn]?" Fry decides that Leela is the one thing worth saving, and allows himself to be frozen so that he may save her 1000 years in the future. Nibbler also refers to Leela as the Other", implying a deeper connection between the two.
Love's a two way street
The viewer is finally afforded a glimpse into Leela's mind in "The Sting", which is set almost entirely in her dreams. From this perspective, it is clear that she cares greatly about Fry as well. When Leela awakens from her coma in the hospital, it is revealed that Fry stayed by her side the entire time, once again demonstrating his continued loyalty and faith in her. They share a tender embrace, but do not become a couple. In "Anthology of Interest I", after Leela kills the whole crew except for Fry, the two are seen in bed, naked, and Fry says he likes the impulsive new Leela. In "The Farnsworth Parabox", Fry and Leela see what their lives would have been if they had got married. In an alternate universe, "Universe 1", Fry-1 and Leela-1 have apparently been married at least one year prior to Fry-A and Leela-A's arrival.
At the end of the original run, in "The Devil's Hands Are Idle Playthings", Fry trades his hands for those of the Robot Devil in order to win Leela's heart with his holophonor, as he was able to do when he last played for her, in "Parasites Lost". Fry's newfound skill wins him great fame, and he is commissioned by Hedonismbot to write an opera. He decides to write the opera about Leela. After Leela is deafened by Bender's airhorn, the Robot Devil makes a deal with her for Calculon's ears. The Robot Devil then crashes the opera, and presents Fry with a terrible choice: Give up his hands and be left unable to complete the opera which may finally cause Leela to return his feelings for her, or lose Leela to the Robot Devil forever. Fry gives up his opportunity to win her heart in order to save her life, and the Robot Devil takes back his hands. After Fry's terrible attempt at playing his holophonor with his regular hands, the audience leaves, except for Leela. As Fry is about to leave the stage, Leela, the only patron left in the audience, stops him, and asks him to play the end of his opera. Fry plays the last scene, in which Holo-Fry and Holo-Leela turn to each other, kiss, and walk off towards the horizon. Unfortunately, Leela's reaction is never shown, although it is clear by events of the next season that Leela still remains "just friends" with Fry.
In Bender's Big Score, Leela's love interest becomes Lars Fillmore, who she claims to Fry is "the only man she could ever love". When she realizes Lars was actually Fry's time paradox duplicate, her statement suddenly gains new significance.
At the end of The Beast with a Billion Backs, after Yivo dumps the universe (except for Colleen), Fry returns to his quest for Leela's love, although she is angry that Fry went out with Colleen. There was no development of the relationship in Bender's Game save for Fry commenting on how he enjoyed riding Leegola, although he could not find an explanation for this.
And it is not until the very end of Into the Wild Green Yonder, that Leela finally returns Fry's affection, and kisses him. The relationship grows stronger in the next seasons
On the other side
Though not together, Fry and Leela get closer and the relationship progresses in season 6.
In "Rebirth", Leela instantly dies along with the rest of the crew (except for Professor Farnsworth), but unlike the rest of crew, she is in an irreversible coma instead of being revived. In his sorrow, Fry creates a robot that is vaguely reminiscent of Leela. Hermes helps him by copying all of Leela's traits into Robot Leela. When Robot Leela first gains Leela's traits, she kisses Fry, not knowing that she is a robot. She discovers she is a robot when Nibbler bites part of her arm off, exposing her wiring. Regardless, she and Fry go on a date. Robot Leela says that she doesn't know if her feelings for Fry are hers, or if they are simply Leela's, so she asks Fry to be just friends with her again, to which he reluctantly agrees. At Leela's funeral at the Cyclophage reserve, Leela is awakened by Bender's obnoxious partying. She is very surprised to find Robot Leela and Fry kissing. On Earth, Leela is upset that Fry became involved with Robot Leela. Fry later talks to himself, saying that he only loved Robot Leela because she was like the real Leela, and that he thought Leela loved him, but was wrong as usual. Leela listens to this without Fry's knowing. When Fry says he was "wrong, as usual," Leela appears to Fry, and tells him that he was "wrong again," insisting that she truly did love him. She forgives Fry and kisses him, telling him that things will work out between them unless Robot Leela is jealous, like her. Robot Leela, being identical to Leela, was indeed jealous and mad when she sees this, and the two Leelas fight over Fry. Then it is revealed that Fry was really a robot. Fry had saved Leela by sacrificing himself during the crash, and Leela was extremely distraught. She built Robot Fry, in the same way Fry, at this point revealed to really be Robot Fry, had built Robot Leela. The two robots decide that they are in love, ditch their "meat suits", and leave together, leaving Fry and Leela to each other.
In "In-A-Gadda-Da-Leela", Leela and Fry's relationship is briefly suggested. As Leela is about to leave for her mission, Fry gives her some trail mix he made, and a large painting of himself for Leela to remember him. Leela asks him to keep it, as it is far too big, and kisses Fry on the cheek, telling him that she will be back soon. Also, after meeting up with the rest of the crew and beating up Zapp, she holds Fry's hand briefly as the V-GINY comes.
In "Attack of the Killer App", it is apparent that Fry and Leela's relationship has been put in minor setback. When Fry and Bender compete to see who can get 1,000,000 followers first on the social networking site "Twitcher" Fry discovers Leela has a singing boil named Susan. He chooses the contest over his affection for Leela, and she is very upset when she finds out. However, when the contest ends in a tie, Fry regrets his desicion and replaces the now-viral video with his own, by diving into a hot tub full of barf. Leela is touched, but only refers to Fry as a friend.
In "The Duh-Vinci Code", Fry asks Leela to have sex in the catacombs under Rome (alluding to the "mile deep club", a reference to the mile high club), and Leela promptly agrees, but the Professor interrupts them.
In "The Late Philip J. Fry", Fry intends to take to Leela out for her birthday lunch. He shows up extremely late, and Leela angrily leaves, having already eaten alone. Later, Hedonismbot throws a bachelor party with strippers, and Bender intends to go with Fry. Leela, initially thinking Fry would be going to the party, is happy when Fry asks her out for a birthday dinner instead. Before he can leave, though, the Professor makes him and Bender test his time machine that only goes forward in time. Fry explains on his video birthday card why he will be slightly late, and tells Leela he loves her. However, the Professor accidentally makes them go 6,990 years forward instead of one minute, and Fry loses his card during their leap in time. Leela is once again disappointed in Fry, and is angry when she thinks Fry, Bender, and Farnsworth went to Hedonismbot's party. She is both sad and mad when she learns that everyone at the party died except for Hedonismbot. For nearly four decades, she stays mad at Fry. In 3050, Fry's video birthday card comes out of time and hits her in the face. An aged Leela now knows that Fry never went to the bachelor party, and is far ahead of her in time, trying to get back. Leela goes into the former site of the Cavern on the Green, where Leela and Fry's date was supposed to take place, and she shoots holes into the porous ceiling. Over the years, the dripping water eventually forms the words "DEAR FRY, OUR TIME TOGETHER WAS SHORT BUT IT WAS THE BEST TIME OF MY LIFE – LEELA". Fry, in the year One Billion, walks into the cavern and sees Leela's message. He decides he had a good life after all, and he, Bender, and Farnsworth skip to the ending of the universe, only to discover that time is cyclical. The three of them skip through the entire history of the universe again and again, and manage to stop only the third time just before they left. Fry shows up for Leela's date on time, and the whole night for them goes along greatly. He confess he lost her birthday card, but she says she doesn't really like cards, and that the only thing that counts to her is their time together. In the final scene, they tenderly hold close to each other on a bridge under the night sky.
In "That Darn Katz!" Leela is seen sitting alone with Nibbler during a night out, lamenting she hasn't a man, as Fry is out on the dance floor with Bender rather than her.
In "The Prisoner of Benda", Leela laments on Fry only caring for her looks and not her inside (and vice versa when saying she is the most beautiful woman in the world). When obtaining the body of the Professor, she thinks Fry is repulsed by her (and he is, but he is willing to lie about it). To prove her wrong, he obtains the hideous body of Zoidberg. Both repulsed by each other, they agree for a date to prove they are not superficial. On the date, however, they start making out, leading to a romantic meeting in the bed, the first known.
In "Lrrreconcilable Ndndifferences", Leela is very saddened by Fry's assumed death. When they realize he is alive, she is very happy. After Fry reads his comic, Leela gives him a passionate kiss on the cheek.
Fry and Leela's relationship hits a major snag in "The Mutants Are Revolting" in which Fry accidentally reveals in public that Leela is a sewer mutant living illegally on the surface, which leads to her exile into the sewers. Fry is similarly banished to the sewers for two weeks for harboring a mutant and takes it as a chance to share Leela’s suffering, but Leela, furious with Fry for ruining her life, suggests he jump into the toxic waste and become a mutant himself if he wants to understand the life of a mutant, though only out of bitterness as she quickly comes to realize she is being too hard on him. Nevertheless, Fry complies and seemingly turns into a hideous blob-like mutant. Leela is deeply moved by Fry's sacrifice and reconciles with him, although she is naturally repulsed by his new form to the point where she refuses to make physical contact with him. The two lead a campaign that allows all sewer mutants to live on the surface, and Leela works up the stomach to kiss Fry in celebration, upon which it is revealed he did not mutate, but was stuck in the mouth of another mutant.
In "Ghost in the Machines", Fry has sex with the Mayor's wife. Leela was apathetic of the situation. Although they share some tender moments at Benders funeral, when Fry has a heart attack, and when the crew visits Fry on the Amish home world.
In "Overclockwise", the relationship is openly described as "on-again, off-again". Leela leaves Fry and Planet Express to make a fresh start, but they reunite and Bender reveals the future of Fry and Leela. The last expression of the two indicates that their relationship lasts until the end.
In "A Farewell to Arms" Fry is shown throughout the episode attempting be gentlemen like to Leela, only to have it subsequently end in disaster every time. During the episode when Leela and Fry are on a balcony Leela is quoted saying: "Fry, stop trying to do things for me!" [She puts her hands onto Fry's.] "Whatever time we have left, just live it with me. So...you wanna join the balcony club?" As Fry starts to smile, Zoidberg interrupts. Fry tells Zoidberg to get lost, and he and Leela kiss. Amy interupts them, so they have to stop their "end of the world sex." Near the end of the episode, Fry tries to save Leela by extending his hand to her, but in the process, accidentally rips off her arm. Leela grabs her torn off arm and ends up ripping Fry's arm off too. At the end of the episode, we see the two arms holding hands in the way they were ripped off, floating in space.
In "Zapp Dingbat", Fry, after suggesting that Zapp Brannigan and Turanga Munda are meant to be married, openly wonders if he is marriage material. Leela responds that he is getting there. During the scene when everyone is cheering after the peace treaty is signed Fry and Leela are shown hugging.
In "The Butterjunk Effect", The two go on a double date with Kif and Amy. Later, Leela refers to Fry as her boyfriend and has a kiss fight with Amy over him. Fry also refers to Leela as his girlfriend
In "Fun on a Bun", Fry and Leela's relationship is confirmed when Leela says that she is "breaking up with Fry" while at Oktoberfest because he was drunk and was embarrassing both himself and Leela. Fry was unaware of the relationship, saying "We were going out?! Wooo!" then becoming upset because he realizes that they broke up. Later on, Fry seemingly gets caught in Bender's meat grinder, as evidenced by the bits of clothing found inside the sausage. Back at Oktoberfest, Bender brings his sausage along to get judged, and he offers Leela a piece. She notices the hair and clothing and comes to the conclusion that she had eaten Fry. Stricken by grief, Leela goes to Annie's Forgettery, where she gets the links between her memories of Fry and her conscious mind removed, leaving her with no memories of Fry. The only memory she has of Fry is the color orange, which causes confusion when she sees it. Unbeknownst to Leela and the rest of the crew, Fry escapes the sausage grinder, although he is frozen in ice and loses his memory. Having no recollection of his time with Leela (except for a sad/confused feeling when he sees a purple horse's tail), Fry joins the Neanderthals who find him and begins to adopt the Neanderthal mindset, that being "loathe all humans". Fry later leads a battle against humans and they come to the surface where Oktoberfest is still being held. The battle goes on and finally Fry and Leela come face to face on top of the Planet Express ship and start to battle. At some point, the hats they're wearing fall off, causing their hair to be visible. Seeing the familiar colors causes them to question if they had met before, and they immediately share a passionate kiss. During/after the kiss, all of Fry and Leela's memories are returned and Fry's forehead returns to normal.
In "Free Will Hunting", Fry and Leela are briefly seen naked in bed together, indicating that they are still in a relationship.
In "Near-Death Wish", Leela hits on Fry in the near death star saying his "confident and take-charge" attitude is a turn on. Fry quickly dismisses her advance since he's "trying to meet old people."
In "Naturama", Fry and Leela are recreated as salmon who fall in love and give birth to children shortly before ending their life cycle.
In "Fry and Leela's Big Fling", Fry and Leela's attempts to be alone are ruined by their co-workers. Leela says "[she's] going home, by [herself], as is normal for [her]", and Fry says "[he] won't see [her] again until the morning". Everyone (with the exception of Scruffy) leaves, while Fry and Leela hide in their lockers. Fry prepares a romantic dinner with stuff around the office, they nearly kiss until they find out Scruffy hasn't left. They then go to Central Park, until Bender mugs them. The two then go to Elzar's Fine Cuisine, and order two giant ants. Fry is about to crack the shell, but accidentally cracks Zoidberg's claw. Zoidberg explains to the two that he got a job cleaning off the dishes at Elzar's Fine Cuisine. Leela suggests to go to her place, but Nibbler is there. The two are upset that they can't be alone, then an advertisement on Leela's wristlojackimator goes off. It advertises a romantic vacation at a resort. They go on the vacation, but it turns out that the resort is a zoo on the planet of the primates.
In "Leela and the Genestalk", Leela undergoes squidification, but Fry still thinks she's Leela, "the woman [he loves]". At the end of the episode, they're holding hands on a street filled with plants.
In "Meanwhile", Fry and Leela got married for the second time, and this one sticks and they grow old together.
Fry: You're smart, you're beautiful, and best of all, you'll go out with me-e?
Leela: Fry, please try to understand: You're a man, I'm a woman. We're just too different.
Leela: You know, Fry, I don't care if you're not the most important person in the universe. It really makes me happy to see you right now.
Fry: Then I am the most important person in the universe.
Fry: I thought she loved me too, but obviously I was wrong, as usual.
Leela: Wrong again. You were right.
Leela: What I'll remember is our time together.
Leela: Fry, can we talk about our relationship?
Fry: Of course. Our relationship is the best thing in my life, so I'm sure I'll enjoy talking about it with you.
Fry: Well, this is the end. There was so many things I wanted to say to you.
Leela: Like what?
Fry: Like this is not the end. But mostly just, I love you, Leela.
Leela: Maybe I waited too long to say this, but I love you, too- WORMHOLE!
Leela: I should have known better than to trust one of Fry's romantic gestures. Every time he says he loves me, I get killed!
Fry: Psst. Leela, wanna join the Mile-Deep Club?
Leela: Sure, why not?
Leela: Fry, stop trying to do things for me! Whatever time we have left, just live it with me. So...you wanna join the balcony club?
Leela: Somehow, I keep finding myself thinking about this place... And things.
Fry: Things like me or things like this badminton racket?
Leela: You, Fry.
Leela: Sean, I'd like you to meet Fry. He and I are...what would you say we are, Fry?
Fry: Nude and interrupted.
Fry: Leela! Oh my God, you saved my life! I am gonna get you so many lizards!
[The Professor has told Fry and Leela that they will all get to live their lives over again.]
Fry: What do you say? Wanna go around again?
Leela: I do.
- This list should include all episodes mentioned above.