Dalek Caan in the Doctor Who episode Evolution of the Daleks. He does a face turn after seeing "the whole of time and space" and bearing witness to the destruction and devastation that his species have caused throughout history. Unfortunately, since he had become insane and babbling, it was a little too late by the time the Daleks had discovered his actions.
Before Dalek Caan was Dalek Sec, who became sympathetic to humans, and horrified of the other Daleks actions after becoming a Half-Human Hybrid. Ironically, it was Caan himself who ordered Sec's extermination
In "Let's Kill Hitler" After the Doctor has been poisoned by Mels, who was raised to kill the Doctor, he whispers something in her ear intended for River Song. When Mels figures out that she is River Song, she uses all of her remaining regenerations to bring him back to life.
The Fifth Doctor's companion, Vislor Turlough, joins the TARDIS crew as The Mole, under orders to kill the Doctor by the Black Guardian, but has a change of heart, defies the Guardian, and remains a loyal companion until his departure.
In The End of Time, The Master realizes that much of his insanity was caused by the High Council of the Time Lords as part of a Time War-related gambit, and ultimately after fighting the Doctor for years joins him in defeating Rassilon and his council.
G'Kar started out the Babylon 5Myth Arc looking deceptively like the heavy, and evolved into the conscience of the entire Interstellar Alliance. This was intentional misdirection of the audience.
Or, as with Londo, he simply changed because the situation had done so and remained the same inside.
The Minbari warrior caste leader Neroon was a true Heel Face Turn.
Bester appears to make one in Seasons 3 and 4, providing significant aid to the rebels, but later on reverts to his true allegiance: himself (and, secondarily, Psi Corps over and above the Earth Alliance government) Not before programming Garibaldi to function as a double agent, however..
Battlestar Galactica: Athena and Caprica-Six. Later, the Leobens, Sixes, and Sharons as a whole. Also, Lt. Kelly during the mutiny.
LOST: As shown in flashback, Juliet had actually gotten sick of the Others some time before she was even introduced on the show. She took the first opportunity she could (being made The Mole) to betray Ben.
Ben himself finally has one part-way through Season 6, but only after having everything he cared about—his daughter, his authority, and Jacob—taken away from him.
The Freighties didn't really know that they were on the wrong side at first, but after witnessing some of Keamy's atrocities, they switch to the Losties' side pretty quick.
Likewise, Charles Widmore, the former Big Bad of the series, suddenly stops trying to take over the Island and returns to fight the evil of the Man in Black after an off-screen meeting with Jacob.
Sawyer too. In the beginning a true Jerkass he gradually becomes more and more likeable before completing the Heel Face Turn in Season 5.
The argument could be made that he actually made the Heel Face Turn in Season 1, when he told Jack about Jack's father.
Fred on Angel does a Face Heel Turn when becoming Illyria, and then ends up doing a Heel Face Turn later that season.
Darla and Lindsey both flirt with a Heel Face Turn at various points, and Connor does a full Heel Face Turn.
Damar, Gul Dukat's Dragon on Star Trek: Deep Space Nine, stays on with the Dominion after Dukat goes off to do his own thing. Eventually, though, he realizes the Dominion is using Cardassia, and starts a resistance movement. He even winds up taking terrorist lessons from old enemy Kira Nerys.
Happens fairly often in Power Rangers. Sixth rangers such as Mighty Morphin's Green Ranger Tommy Oliver and Lightspeed Rescue's Titanium Ranger Ryan Mitchell have started out evil.
In Space actually had the Big Bad, Astronema, briefly join the rangers after finding out that The Hero Andros was her long-lost brother. While she originally intended to betray the Space Rangers and thus secure her place as Dark Specter's chosen heir, she ended up siding with them, and was even declared an honorary Power Ranger herself. While Dark Specter and Darkonda recaptured and brainwashed her into an even more evil Astronema v2.0, she was restored to her true self, Karone, and later took over the position of Lost Galaxy's Pink Ranger.
Also Jarrod and Camile from Jungle Fury even though Jarrod was possessed he still had a change of heart.
Another example from Lightspeed Rescue is Diabolico, who starts off as the Big Bad, then becomes The Dragon when Queen Bansheera reveals herself, then dies at the Rangers' hands and has his powers transferred to Impus, Bansheera's son. The latter becomes Olympius, and has no intention of sharing his power, which results in the other two Elite Mooks, Vypra and Loki, reviving Diabolico. In the end, Bansheera shows that she's willing to sacrifice all of them for her sake, and even forces Diabolico into killing Loki, his best friend who was blindly loyal to Bansheera. In spite of Bansheera's best attempts to make Diabolico Brainwashed and Crazy afterwards, his loyalties lie with the rangers from that point on until his second death. And the clincher? His ghost is what ultimately saves Red Ranger Carter from making a Heroic Sacrifice to defeat Bansheera forever, taking on that role himself.
Super Sentai too as some of the aboves counterparts had their own Heel Face Turn. Burai, Tommy's Zyuranger counterpart and Rio and Mele Jarrod and Camile's counterparts from Juken Sentai Gekiranger.
Both Crais, and then Scorpius start off in pursuit of our heroes before they end up joining the crew in Farscape. Aeryn is the original one to pull that move. When you see that video of what she used to be like three cycles ago...whoah.
Rak'nor during Season 4 of SG-1, in turn saving Teal'c.
Michael in Stargate Atlantis season 2 episode 'No Man's Land' (it doesn't last; repeatedly getting screwed over by the Designated Heroes drives him back into villainy, and Ladon Radim in 'Coup D'etat.
Sylar on Heroes had the shortest Heel Face Turn in recent memory, lasting only partway through season 3. And both a Heel Face Mind Screw and a straight turn during season 4.
More permanent examples would be Mr. Bennet towards the end of season 1 and Daphne during season 3, at least until she died.
Occasionally used in the 60s spy series The Man From UNCLE. Sometimes the U.N.C.L.E. agents manage to subvert a THRUSH operative into working for them (e.g., the second season episode "The Arabian Affair", where Solo informs a THRUSH minion who is due to retire that THRUSH liquidates retired minions to insure their permanent silence), whereas other times the villain comes over to the good side for his own reasons (e.g., the second season episode "The King of Diamonds Affair", where diamond thief Rafael Delgado decides to betray his organized criminal allies, free Solo and the Girl of the Week, and help them escape).
30 Rock uses this in a Show Within a Show that Jack's girlfriend's grandmother watches. The villain, Generalissimo, looks exactly like Jack, so Jack uses Executive Meddling to make the Generalissimo a good man who loves old Puerto Rican women, scratching lottery tickets, and going to McDonald's to order only coffee.
Layne Price in Mad Men moves in this direction when he agrees to Sterling, Cooper, and Draper's conspiracy; he completes it with gusto when he delivers his "Happy Christmas" to St. John, who had been pushing him around.
In Deadwood, Al Swearengen starts out as the villain of the series, stepping on a prostitute's neck in the first episode and quickly getting into a rivalry with the honorable main character, Seth Bullock. However, the more Hearst influence insinuates itself into the town, the more heroic Al becomes, forming an alliance with other sympathetic citizens and working to thwart the new Big Bad. He's still a total bastard.
Krika in BIONICLE would have had one, if Gorast hadn't killed him.
Vezon, after he lost the Mask of Life.
Lionel Luthor, in Smallville, who starts out as a ruthless businessman, bad father, and the Trope Codifier for Magnificent Bastard, undergoes an abrupt about-turn while in prison. His devotion to a life of poverty and charity work is short-lived, however, as a fight with Lex motivates him to return to ruthless tactics, ostensibly to actually protect Lex... And then he finds himself serving as a conduit for Clark's dead father, Jor-El, repenting for his past acts, devoting his life to protecting Clark, and suffering from really bad migraines. Unfortunately, all of this is so confusing that no one actually believes that he's a good guy when he begs them for help. He is eventually killed by his own son, Lex, after which Clark finally learns, once and for all, that Lionel had been on his side in the end, dying to protect Clark's identity as The Traveller from Lex. Clark acknowledges that Lionel was the third 'father' who had died for him, and honours him the same way he honoured Jonathan Kent - by pouring a handful of dirt on his coffin.
Metallo pulls one in Season 9, after a restructuring of his system purges him of the adrenaline rush that heightened his aggression and made him evil. Since the comic book character is still evil though, there's no telling if it will last.
More recently, Brainiac appears to have turned to the side of the angels. He now calls himself Brainiac 5 and is a member of the Legion of Super-Heroes, claiming that they and Clark "cured" him of his evil. He returned to the present to aid Clark by 1) preventing Smallville High's student councilor from trying to kill Clark at his high school reunion and 2) showing him his past, present and future, to help Clark get over his misplaced guilt over Pa Kent's death and his fear of the future, and move toward his destiny. Since this is due to reprogramming however, it may not count as genuine. Made even more muddled by the fact that this version of the character was reprogrammed into performing a Face Heel Turn in the first place before the destruction of Krypton.
Tess Mercer is also attempting one of these as of Season 10. Given her Heel Face Revolving Door track record, it's hard to see where she'll end up. So far though, she's stayed loyal, even shooting down Earth-2 Lionel's offer to become the father she never had.
She stuck with it right to the end of the series, when in the Grand Finale, she uses her last breaths to give a last-minute verbal Take That to Lex and wipe his mind with a neurotoxin, ensuring that he cannot use any of the knowledge he accumulated since the beginning of the series against the newly dubbed Superman.
No mention yet of Sue Sylvester? Not only did she rank New Directions top amongst the other teams in Sectionals, she was also entirely responsible for the club staying open another year, despite having spent the past nine months continually trying to close it down.
Well, Sue only allowed New Directions to live because she loved hating it so much.
Castiel on Supernatural had a very very gradual Heel Face Turn over the course of Season 4, although nobody knows until the final episode that the angels are the bad guys, so although the change in loyalty is gradual, the act of changing sides appears to happen quickly.
It almost happens a couple of episodes earlier, but his superiors catch him, prompting a brief Face Heel Revolving Door situation.
We catch glimpses of that trope throughout the season, with Castiel frequently deliberating between his orders and his increasing sympathy for Dean.
The 1998 Merlin series has Lord Lot and Lord Ardent, who are originally generals opposing the main characters but later become their allies.
Margaret Houlihan has a very well-orchestrated one on M*A*S*H, which takes place over the entire fifth season, with a pivotal episode called "The Nurses," which Loretta Swit says is her favorite episode. Two other important episodes are one where an old friend of hers visits, and tells her that not just her pierced ears have closed up, she has, after which she makes a deliberate effort to be more open with others, and the two-part episode where she is stranded with Hawkeye under fire. The great part of the story arc is that while the character softens, and becomes kinder, and warmer toward people, she does not lose her "regular army" bearing, and there's no retconning of her earlier coldness, so it is real character growth, and not a reboot.
In Garrow's Law, right at the very end, Sir Arthur Hill turns the tables on Lord Melville by exposing corruption at Garrow's instigation - and in the last scene he is shown giving Garrow and Sarah his blessing as they embark on a new life together. Quite amazing, given the animosity he has exuded throughout the series.
Warehouse 13 has Claudia Donovan, initially seen as an antagonist. Early in Season 1, she hacked into the Warehouse to get to Artie, blaming him for her brother's victimization to an artifact and trying to have him help her bring him back. Once that succeeds, she's proven to be an overall good person, and becomes the Warehouse's Techno Wizard, and later a fully fledged agent.
Another example is Helena Wells, Big Bad of Season 2 who is forced to see the error of her ways and reforms, becoming an ally starting in Season 3.