Garai from Osamu Tezuka's MW started out as a violent gangster who molested a nine-year old boy, but he became a priest to try to atone for his evil ways.
In another Tezuka work, Phoenix: Karma, widely considered to be his greatest masterpiece, Gao, a murderous bandit, is inspired to become a pacisfistic, nature-loving artist by the teachings of the Buddha. What makes this example interesting is the contrast provided by the other main character, Akanemaru, a carver of Buddha statues, who starts out as a decent enough guy, but gets involved with the politicians who are trying to use Buddhism as a state religion to control the masses & turns into a vain Jerk Ass who thinks nothing of sacrificing the lives of countless workers to build his giant bronze penis extension Buddha.
The French-Belgian comic book series Odilon Verjus is about a former pimp who has become a Catholic missionary, though in his case, while the embrace of the faith was sincere, there was no particular desire for atonement.
Allronix loves this one. In Through A Diamond Sky, the Dragon has second thoughts when she realizes her boss plans to kill the Creator. In her Tin Man fanfic "Tin," Wyatt Cain slowly renounces revenge and re-dedicates himself to the oath of his office and the Unnamed God through the events of the miniseries.
In the movie Dragonheart, the main character spends most of the film as a rogue outsider tricking townspeople into giving him rewards ... until he stumbles across a talking statue of King Arthur and gets reminded of his oath of knighthood. Although this isn't strictly religious, it has the same Renewal Of Lost Faith aspect.
Pirates of the Caribbean: Dead Man's Chest: Discussed and Played for Laughs. In their first scene in the movie, Pintel and Ragetti talk about how they are going to read The Bible and become "good men". They revert to their piratical ways pretty soon.
The Butterfly Effect: In the alternate timeline where Evan stops the mother and baby from approaching the dynamite-filled mailbox and losses his arms in the process, Kayleigh's psychopathic brother Tommy ends up as a polite and well-kept Christian young-man.
In The Quick and the Dead, Cort was Herod's former right-hand man, who abandoned his violent career in favor of a peaceful religious life after Herod forced him to kill a priest who nursed him and Herod back to health once. Herod has Foy and Ratsy burn Cort's mission to the ground and force him to join the competition.
In Bernard Cornwell's Nate Starbuck series, set in the American Civil War, Colonel Swynyard goes through one of these when an extremely near miss from a cannonball results in him waking up lying in the battlefield mud next to a religious pamphlet. Interestingly, this is played completely straight (and works extremely well) by an author who had, in other series, tended to treat Christianity as a Corrupt Church, verging on Religion of Evil.
It wasn't Christianity in general he was bashing in those other works, but the Catholic Church of the period not long before the Protestant Reformation, which even the modern Catholic Church admits was incredibly corrupt. Outside of that, it was individual corrupt priests that he was very hard on.
Cornwell's major works were set in the early 19th century, the later 9th century and the mediaeval period. The Catholic Church of those era was pretty corrupt and unpleasant. It is also worth noting the benevolent treatment that individual priests get, like Father Curtis/ El Mirador, Father Beocca (who actually performs a feat of badassery that impresses a band of Bad Ass vikings) and Father Pyrlig, get.
Jean Valjean of Les MisÚrables starts off as a thief, hardened and not so nice, even going as far to steal from the only man who gave him shelter. This man, however, happens to be a bishop, and gives Valjean more money, telling him that 'he has bought his soul for God'. Valjean repents and becomes #1 dogooder. Javert doesn't care.
In Sergey Lukyanenko's Seekers of the Sky duology, the main characters are on the run from the entire nation. At the end of the first book, they are cornered by the Guard, headed by a huge Austrian officer named Arnold (guess). Then Marcus creates a small miracle, causing Arnold to immediately switch his allegiance, believing the kid to be the new Messiah.
One epigraph from Elminster's Daughter invokes this in a typical Realmslore fashion. It's a quote from a book named "Tyrant's Throne to the Arms of a Goddess: My Road To Mystra".
In another Forgotten Realms novel, War in Tethyr by Victor Milan, this is implied to be the case for an orog paladin of Torm. Details of how an underground orc ended up in the service of the god of duty are unknown, but he avoids talking about his past and even abandoned his given name.
Sam Slater in Strawberry Girl is evil, before Brother Jackson, a traveling minister, tells him "the harm of drinkin' liquor, and of swearin' and backbitin', gossip and anger" and prays "extry hard" for him. Also, Slater's family had nearly died of unspecified illness while he was away, and he became sick when he got home.
Zed Arthen in the Heirs of Ash books used to be a Paladin of the Flame, but abandoned his church and fled after seeing terrible massacres committed in the name of righteousness. His apathetic cynicism when we first meet him starts fading when he starts to recover his faith.
In the Dale Brown novel Sky Masters General Samar used to be a brutal member of former president Marcos's Secret Police. Then he became a Muslim and changed for the better.
Aeron Greyjoy in A Song of Ice and Fire nearly drowned and had a Near Death Experience, resulting in him converting to the faith of the Drowned God as a priest and becoming a more moral person, (although this is Westeros, so that just means a lighter shade of grey).
May have happened to Sandor Clegane, if the large man with a limp Brienne saw was him. He has previously renounced all gods, but the man Brienne saw was digging graves for a priest — a former knight who'd undergone this trope years before.
Also Lancel Lannister, after undergoing a near fatal wound and out of guilt over his involvement in the murder of the previous king and sleeping with the Queen Regent, joins a Church Militant and repents his sins. This causes problems for the Queen Regent, who finds herself charged with murder and fornication.
Occasionally occurs in Safehold when clergy of the corrupt Church of God Awaiting rediscover their faith. The two primary examples include:
Archbishop Erayk Dynnys, who rediscovers God while awaiting execution. He proceeds to proclaim the Church of God Awaiting as being in the wrong, guaranteeing a death dragged out by Cold-Blooded Torture, rather than confirm the Church's version of events and get a quick and easy death.
Vicar Rhobair Duchairn, a member of the Group of Four, the vicars who really run the Church of God Awaiting. He begins to rediscover his own faith in the wake of the disastrous battles with Charis in the first book. While not siding with Charis, and unable to truly break away from the Group of Four even if he wanted to, he slowly but surely turns into a Good Shepherd who does his best to make sure the poor and destitute of the Church's capital city are looked after and becomes the chief voice of opposition against Grand Inquisitor Zhaspahr Clynthan.
From Provosts Dog, this is Goodwin's backstory. She was once a loose Dog, until a shipment went skewed and she was left dying in a ditch. She pleaded for the Goddess to let her live, she survived, and she became the Goddess' Magistrate in the Lower City as well as one of its best Dogs.
Shepherd Book in Firefly seems like he went through this. But as revealed in his origin, he's more of an example of The Atoner. After spending decades as The Mole in the Alliance for the Browncoats, he had performed numerous atrocities, some to keep his cover, others to advance the Browncoat's cause. After a strategic loss, he's ousted and homeless, finding God under the supervision of a soup kitchen preacher.
In Deadwood, Tolliver's associate Andy Cramed leaves the life of crime after he develops a near-fatal case of smallpox and gets dumped in the forest to die. He returns to Deadwood later as a reverend and reformed man. Tolliver can't stand Cramed's shift in allegiance and provokes him to the breaking point, getting a shiv in the gut for his trouble. Old habits die hard.
Used along with Faith Heel Turn in My Name Is Earl. A Scary Black Man gangster who went by "Hash Brown" and eventually became a priest ends up being on Earl's list at least five times, with each new list item revealed making him angrier and angrier until he snaps and decides to return to his gangster life. Then Earl recognizes his car and reveals that he broke the taillight on it (another list item). The broken taillight caused Hash Brown to get pulled over and be late for a deal which ended up turning into a brutal shootout, meaning that Earl had indirectly saved his life. Since this event was what had caused him to take up religion in the first place (he originally attributed it to divine intervention), he thanks Earl and goes back to being a priest.
Another person on Earl's list was Donny, a former violent criminal lunatic who found religion while serving two years in prison for a crime Earl committed. Donny forgave Earl almost immediately, reasoning that if he hadn't gone to jail he wouldn't have cleaned up his act.
MIKE/Phillip Michael Gerard from Twin Peaks used to be a serial killer who raped and murdered women with his accomplice BOB. However, at some point, he "saw the face of God". He cut off his left arm to rid himself of his "Fire Walk With Me" tattoo (which symbolized being "touched by the evil one"), and even helps the main characters solve the mystery of Laura Palmer's murder.
The Lewis episode "The Point of Vanishing" features an inversion, in which a former religious activist who once tried to kill a prominent atheist author gains redemption after losing his faith in prison. Unfortunately, his attempts to make reparation lead to his own murder.
Willy Thorndop, the Marksmanship master in Arcanum, was pretty much your stereotypical "Evil Gunslinger" in his younger days. One day, he was at a bar, drunk off his ass and shooting his mouth off about his skills, and was challenged to a gunfight by a teenaged boy. Without missing a beat, Willy pulled out his gun, pressed it against the boy's head, and pulled the trigger. When he sobered up, he was so horrified by what he did and what he had become, he just ran, eventually seeking refuge in the priesthood of Halcyon. As penance, they made him cut off his thumbs and index fingers so that he could never use a gun again.
Dragon Age: Origins has Leliana, a former spy-for-hire (and sometimes assassin) who got religion after being betrayed by her mentor/lover.
If you complete Thane's loyalty mission in Mass Effect 2, Kolyat Krios, his estranged son, will have quit the life of crime and turned to religion by the time you meet him again in Mass Effect 3.
Joshua Graham from Fallout: New Vegas. He was originally a missionary of the New Canaanites, before helping to create Caesar's Legion. After being dishonored, set on fire and thrown into the Grand Canyon by Caesar, he found his way back to New Canaan and the Mormons. It mellowed him out. A bit.
Used as a hasty Deus ex Machina in Shakespeare's As You Like It. Duke Frederick, the usurping villain who sets the plot in motion by driving the heroes into exile, is on his way to make war with the heroes, when he comes across a religious hermit who convinces him to give up his evil ways and lead a monastic life. We're told all this after the fact via messenger. Loose end officially tied up!
Memphis has an interesting take on this trope. Huey's mother is a prejudiced, racist "Christian." Then she attends a black church and becomes accepting.
A Double Subversion in the musical The Book of Mormon. In act 2, Kevin Price marches up to the genocidal warlord-dictator, singing "I Believe," over-the-top in his idealism and his conviction. The general is unimpressed, and shoves the book up Price's ass. However, at the end of the show, with a confrontation from both the missionaries and the Ugandans, the general converts and ends up ringing doorbells at the show's conclusion.
Done in There Will Be Brawl. Mario is quick to blame Bowser for Peach's disapearance, but is reminded by Luigi that Bowser gave up such things when he became a Buddhist. Later in the series, we get to see Bowser. He is dressed in a Chinese-style robe while meditating in his garden, and begins dispencing philosophy when questioned. Until his Taking You with MeHeroic Sacrifice against an army of Game & Watches.
Season 16 of South Park may have pulled this with Cartman when he converts to Judaism. Not that he'll ever be good, but his antics have been much less of a psychotic sociopath and closer to the Spoiled Brat or Jerk Ass persona he started the show with.
American Dad! had that episode where Stan made friends with an Atheist so to get him to turn to God, he subjects the man to a thorough Break the Cutie process. Instead of turning to God, he committs suicide and comes back by making a Deal with the Devil. Stan at least learns to accept him for who he is.
Perhaps one of the most prominent examples is the Apostle Paul from the Bible, who prior to his conversion sparked by the trope-codifying bright-light and booming voice of God from heaven was (by his own admission) a ruthless Knight Templar of a Pharisee, who violently enforced the letter of the religious law with an iron fist, dragging Christian families out of their homes and taking part in stonings. After literally seeing the light, this man went on to record more than half of the New Testament and lay the foundations for the church all over the Roman Empire.
Malcolm X is perhaps best known as a leader in the Black Power movement, to the point where he is the Trope Namer for the "black liberal strawman" character type. What's less well-known is that, after he made the hajj and met Muslims of all races, he renounced Black Power, feeling that it was antithetical to the basic tenets of his Muslim faith, and given to the belief that religion could unite everybody. This wound up becoming a Real Life case of Redemption Equals Death, as his conversion led to his assassination by members of the Black Muslims, who felt that he had betrayed the movement.
X is actually a double example, as he discovered the Nation of Islam in prison, during a period where he was so violently anti-religious that the other inmates called him "Satan".
Many, many more examples, of which we will list only a few here.
Saint Ignatius Loyola was a soldier and fighter who fought in many battles. After suffering an injury on the battlefield and heading home to heal, he started reading philosophy and theology to relieve his boredom- and then became the kind of man who gets Saint added to his name.
Saint Augustine had a pretty R-rated lifestyle (promiscuity, partying, etc.) before his conversion.
Saul was a Renegade Jer who enforced and taught the law.
Ermahgerd, Saul were a Jer.
The Apostle Matthew was a tax collector, which typically had a reputation for dishonesty. Jesus up and decided he'd make a good disciple and next thing anyone knew a reformed Matthew was better known for his Gospel writing than his money swindling.
Saint Christopher was a fighter and a brawler who converted and gave up his ways.
In some versions, he was a dog-headed 15-foot giant who was looking for the strongest leader in the world. This eventually led to him running around as a bandit in Satan's gang, until he saw Satan scared of a cross and went looking for Jesus.
Rabbi Shimon ben Lakish was a bandit before he was convinced to 'give his strength to the Torah'. When his mentor mentioned his past in an argument, the shame pretty much killed him.
St. Vladimir was a bloody tyrant who had murdered his own brother and practiced Human Sacrifice, before turning to Jesus.
Constantine deliberately abused this trope to sin without consequence - he believed in Christianity, but knew that it allowed only "one baptism for the forgiveness of sin," so he delayed his official conversion (and baptism) until he was on his death bed to guarantee he would die with a clean soul.
Actually, death bed baptisms were fairly common, and not a case of Constantine abusing it. Another version says that Constantine basically couldn't convert to Christianity, despite converting the rest of the Roman Empire, because the emperorship was still a pagan position.
Alabama Governor George Wallace repented his former outspoken pro-segregation views upon becoming a born-again Christian. And, you know, that whole being shot and crippled thing.
Wallace once stated in private he didn't really believe any of that pro-segregation stuff...but he wanted to be elected and in the South that meant going along to get along. So after his chances to be politically relevent were gone he dropped it since he didn't really have it to begin with. Not entirely sure if it counts but if true it counts as a Real Life version of Just Between You and Me.
Joshua Blahyi General Butt Naked (more in Wikipedia. Liberian Warlord, human-sacrificer, and general homicidal maniac. After a theophany in 1996 gave up his past life and became a Christian preacher, opening a mission to help former child soldiers and members of rebel groups (including several guys who used to be his enemies). As far as can be judged without knowing the contents of his mind, he seems to be legitimate in his desire to fix the country. He has even expressed a willingness to be tried for war crimes.
According to this interview, many retired Japanese Yakuza bosses become Buddhist priests. Subverted in that most of the time, their motives are at least partly cynical.
John Newton, lyricist of Amazing Grace, was at first slave trader who barely survived a powerful storm. After that act, he became a preacher and fought against slavery.
Not quite. Newton found God in 1748, left the slave trade in 1755, was ordained as a priest in the Church of England in 1764, wrote the lyrics in 1772, and began regretting his part in the slave trade and speaking out against slavery in 1780, 32 years after after first converting to Christianity.
Johnny Lee Clary, a former Ku Klax Klan leader who, after being inspired by a black preacher's bravery and displays of faith, became a Pentecostal Christian and teaches against hate groups and racism.
Mehmet Ali Agca shot Pope John Paul II. After the Pope recovered from his injuries, he visited Agca in prison. Agca is now a Catholic.
Subversion with prisoners: A news article described how prisoners discover religion, get a pardon or commuted sentence, only to commit another crime. Further, some poorly-constructed faith based prisons caused some criminals to rationalize their crimes (although this study could use a larger sample size).