
Even though it is technically their show, I promise to be just as fair with these two as with any other.
What evidence is there that they could work?
Well, it is their show…. ^_- (oops, didn’t I just say I would….never mind)
Relena chases Heero around the world, not only for her sake but to keep Heero from fighting (um…eps 1-20, basically).
Just moments after Heero almost kills her, Relena places herself between him and Duo in an act of protection (ep 2)
When Heero comes to the Sanc Kingdom, she hurries to greet him, and then is content only to watch him. (ep 3?)
Relena is constantly speaking Heero’s name out loud to herself for no reason.
Heero is constantly speaking Relena’s name out loud to himself for no reason.


When Heero is about to let himself die by not releasing his
parachute, it’s Relena’s voice that reaches him and causes him to attempt to
save himself. The fact that afterwards
he was angry with himself indicates that he honestly intended to die, and was
influenced by Relena otherwise. (ep 3)
Heero didn’t kill Relena even after she “knew too much,” and even saved her life when Une attacked the school (ep 6).
Heero decides to fight for the Sanc Kingdom, and saves Relena again during the battles with OZ (ep 3?)
Heero rescues Relena again from Libra, and swears to protect her. (ep 4?)
When about to depart to fight Zechs, Heero pulls Relena closer to him and tells her, “I’m going to come back [to you]. This is all I can do for you right now.” Not only is this a rare declaration from Heero, as he never shares such personal intentions with the other pilots, but there is no other scene in which Heero physically reaches out to another person and pulls them closer to him (without killing him ^_^). Not only that, but he was smiling through the entire exchange. (ep 48)
(By the way, Heero technically says, “I’m going to come back.” However, his choice of “kaeru” instead of “modoru” for “come back” indicates that he is not simply “returning,” but “coming back” to a certain place, i.e. home)
At the end of the series, Heero gives Relena a happy birthday card and a teddy bear. I don’t know if this is significant, but my friend once told me that there’s some Japanese legend implying that you give a teddy bear to someone you love (which, as I'm told, is true). But then, I can’t really argue any conscious symbolism on Heero’s part, since I’ve already argued that he is Japanese in ethnicity only. And the teddy bear has significance to the little girl from Endless Waltz. But in any case, he went through the trouble to give it to her. (ep 49)
In Blind Target and Endless Waltz, Heero instantly rushes off to Relena’s rescue when she is kidnapped/in danger.
At the end of Ground Zero, Heero agrees that he will visit Relena from time to time, and allows her to fall asleep against him.

This scene from Endless Waltz.
And this scene which includes free-floating geometric
shapes, a indication of definite attraction.
Heero meeting Relena is the first real contact any of the Gundam pilots has to anyone from outside their mission. To Relena, Heero is everything she needs at this time; someone to support her through a very difficult time. As someone who has grown up being the center of attention, one more lackey wouldn’t suit her—she needs a man who’s her equal. To Heero, Relena is a symbol of the future he’s fighting for. She’s strong, smart, and sympathetic to the colonies—his cause. Heero Yuy would not fall for someone who was superficial; he also needs an equal, someone who he can protect while at the same time respect.
What evidence is
there that it wouldn’t work?
Heero obviously tried to kill her a couple times. (ep 2, 6)
Heero promises not to leave the Sanc Kingdom without telling Relena, and then immediately leaves to fight with the Treize faction against OZ (ep 3?)
By the end of the series Relena is the Vice Foreign Minister of Earth. She’s a very famous person and has a strong influence with everyone; in other words, if she were to get together with anyone, everyone would know about it. Heero is just now starting to figure out how he wants to live his own life, so being in a public spotlight might be too much for him. Up until now he’s survived by laying low and keeping secrets—it’s going to take more than a crush to pull him out of that. And even if Heero did commit to Relena, it would still be difficult for him to adjust to such an open lifestyle.
More than that, the affection Heero and Relena share isn’t always focused directly on each other. It’s possible that Heero is determined to protect Relena to make up for the young girl and her dog—he sees Relena as someone pure and innocent, like that girl, and in the end gives her the teddy bear maybe as a symbol of letting some part of his guilt to rest. Perhaps even as a plea for forgiveness. As far as Relena is concerned, Heero is her “prince” that came at just the right time. She likes being with him because he makes her feel stronger, and because he gives her hope. It’s not too hard to believe that Relena might have attached herself to one of the other pilots had she met them first.
The other factor is that Relena is the first girl his age that Heero has been around (assumed). That, and combined with the fact that she stands up to him, is something Heero isn’t used to. It may be that Heero has an affection for Relena simply because she’s someone different than anyone he’s ever met. Considering the situation this pair is thrust into, it would be strange if they didn’t at least form a strong understanding of each other, if not love.
Relena is without a doubt in love with Heero on some level, and there’s enough evidence to indicate that Heero returns that affection, if only internally. However, their difference in lifestyles would probably prevent them from pursuing any kind of prolonged relationship. In all likelihood they will contact each other once and a while, as two people who struggled through and survived an ordeal together.