Colonel Kati Mannequin is this. She's totally serious, hard nosed military officer who happens to have a Dogged Nice Guy in love with her. She originally uses his crush to positively motivate him to follow orders, but he starts growing on her with his Undying Loyalty, and eventually she cries when she thought he died. In truth he survived, and they got married.
Gundam 00 has Tieria Erde. He's shown as a cold, reserved Deadpan Snarker with not a lot of regard for others, but after his fellow Gundam Meister Neil "Lockon Stratos" Dylandy saves his life, he starts showing more and more emotions and becomes extremely devoted to Lockon. After the four year time skip, he seems to even enjoy having conversations with his and Lockon's partner Setsuna F. Seiei, someone he often used to imply he wanted dead. So it seems he's pretty much grown out of it unless he has to communicate with Neil's brother, Lyle — then he just frosts up. Understandable, to some degree: Lyle is Neil's twin brother who has taken up the "Lockon Stratos" mantle in Celestial Being... four years after Neil's tragic death, whom Tieria might (or not) have fallen in one-sided love with. As the second season advances, Tieria keeps defrosting and exploring his more "human" side...
Then there's Feldt Grace, another Gundam 00 example. She was pretty much the textbook Emotionless Girl (possibly caused by both of her parents dying in a system test of Nadleeh's predecessor unit when she was little) until she started having a crush on Lockon, the defrosting culminating in his death causing the formerly cold and official Feldt to bawl her eyes out while clutching his Haro - the only other person who did that was Tieria. Despite his death, she continued the defrosting and in the second season, she's pretty much a normal if somewhat polite woman.
Motoko Aoyama from Love Hina who was probably the hardest shell among the girls Keitaro had to break considering she was always on the defensive. As it turned out she had a good reason. Her attitude stems from her older sister whom she worshiped like an idol till she got married. Since then she blames men as a way to cope with the shock.
Sesshoumaru starts out supremely arrogant, concerned only with his own status and power, and willing to kill anyone who gets in his way; by the end of the series he is... still supremely arrogant, but has acquired a Morality Pet and developed into an Anti-Hero with a habit of conveniently just passing through.
And also Kagura, who warms up to Sesshoumaru, Inuyasha's group, and especially Kohaku.
Layla Hamilton seems at first to be an arrogant, ultra-perfectionist bitch who loves treating newbies badly at the beginning, but soon we see that she's as hard (if not more) on herself as she is with others and that she loves the Kaleido Stage as much as Sora does. To the point of sacrificing her circus career to gain the Kaleido Stage back from Yuri Killian and foil his revenge on Kalos Eido.
A male version with Fakir, as well, though his case is the opposite of Rue's. Most of the first season he's borderline abusive towards his best friend, Mytho, and comes off as incredibly coldhearted and selfish. Around the same time Rue's dark side appears, his nicer side emerges from time to time and we learn why he's been acting like an Ice King through his backstory. By the second season, he's become much nicer and even downright Adorkable at times.
Sakura also seems to be apart of this trope since she greatly misunderstood Naruto at first, viewing him as a simply an annoying idiot, but now knows the real Naruto and is warming up to him.
Natsuki Kuga from Mai Hi ME, largely the result of being friends with Shizuru, Mai, and Mikoto, as well as Shizuru's love for her. The ice that she uses as a weapon doesn't defrost, though. Her Mai-Otome incarnation also defrosted and opened up to others after meeting Mai at Garderobe.
Sheryl Nome of Macross Frontier is the archetypal example. She starts out as the "Galaxy Fairy," an Idol Singer loved by all, tremendously arrogant and haughty. However, her meetings with Alto Saotome (who refuses to take any of her crap) and Ranka Lee (whose innocence and optimism rub off on Sheryl) change her outlook on life, making her a much more sympathetic character. Of course, the series goes one further by giving her a fatal illness and doing everything possible to Break the Haughty, which only makes her even more human.
Ai Shinozaki from Corrector Yui starts as the local Snark Knight, snarky and aloof and really disliking to team work. Slowly, we get to see how she was a Cheerful Child until her dad's death, how her mother's accident affected her, and how Yui's persistence and optimism is slowly thawing her...
Nami. At first, she claims to only want to work with the crew to accomplish her goals, and maintains that for a little while before she eventually betrays them to steal their money. But by that time, she had grown so comfortable with them that she didn't want to leave; even her own sister remarked that it had been a long time since she had seen Nami so emotional.
Nico Robin even more so than Nami. Goes from "betray everyone to survive", a philosophy that she had had for twenty years, to "sacrifice yourself to allow your True Companions to escape", after about a month with the Straw Hats.
Boa Hancock also serves as this, to an extent. She is at first portrayed as a misandric Ice Queen that clearly lives by the "Screw the Rules, I'm Beautiful!" philosophy, mixing in some Alpha Bitch along with that. Then along comes Luffy, and one Defeat Means Friendship later with her younger sisters, in which he protects them from having their darkest secret revealed, she pours out her heart to him and pretty much immediately afterwards, she falls in love with him.
Ruki Makino from Digimon Tamers. She even gets a new shirt to make it official. To elaborate: The classic shirt she was pictured with during the entire series showed a broken heart, possibly to emphasize her "rebellious" or "not willing to take sentimental crap" attitude. After she defrosts, her mom buys her a new shirt - the exact same one except with the full heart. Ruki wears it for the rest of the season.
Mikagami Tokiya, the resident ice / water guy. He starts out as a loner brooding over revenge, cares nothing else than that, or Yanagi (who resembles his dead big sister) and is extremely ruthless. However, with further interaction with his friends and the realization that revenge is getting him nowhere and would eventually kill him empty handed, he becomes a warmer individual, while still snarky.
Rasen, a completely pale Emotionless Man who thoroughly believed that he had his emotions erased thanks to his Madogu. Until he realized that he hadn't lost his emotions at all. Then in the epilogue, he could at least talk casually...
Kurei, the supposed 'Big Bad', flip-flops between this. Growing up in the village where he is persecuted just for being 'cursed' (turns out they're wrong) makes him cold, this gets carried over when he is sent to the future, until he meets his soon-to-be stepmother Mori Tsukino, in which he starts warming up... until her husband Mori Kouran noticed his power, takes away his mother, and promptly freezes him up again. Until a girl named Kurenai arrives in his life, gives him the first slap ever, and he starts warming up again... until Kouran blew her up, prompting Kurei to get cold again. He spends the majority of the series being a huge asshole, but after he got his ass kicked by Recca, he slowly starts to show signs that he has been defrosted, made much more obvious in the epilogue.
This is basically the entire dynamic between Limone and Dominura in Simoun, with the former making the latter realize her repressed emotional side and evolve away from a heartless manipulator she is first introduced as. In fact, Limone's Fan Nickname is "Icebreaker" in recognition of this feat.
Nadia from Nadia: The Secret of Blue Water. She initially comes across as a cold, aloof pessimist with no interest in communicating with other people (except animals, notably her pet lion cub, King). She also has a very vicious and somewhat sociopathic temper and stubborn, unbending views about the world. However, she finds herself falling for Jean, and the unlikely relationship that develops between them slowly transforms her, bringing out her caring side as she learns to trust others. There are a few moments when she sometimes lashes out at Jean, but he always forgives her. Likewise, when Nadia isn't brooding over her relationship with Jean, she goes out of her way to do nice things for him (cooking, encouraging him to build a gyrocopter, and even comforting him about his father's death). In fact, they get married at the end. There are at least two moments in the island/Africa arc which are intended to show their friendship turning romantic (a kiss and later, when she admits that Jean is more important to her than the Blue Water in Episode 31). Unfortunately, the writers quickly press reset on their relationship after said "developments" occur in the filler arc. (Episode 35 acts as though most of these events never happened, which is why it is best to disregard them from the continuity of the story.)
Lala Ru from Now and Then, Here and There starts off hating all of humanity after all she's been through; by the end of the story, she has sacrificed herself to keep humanity alive by restoring water to the dead Earth.
Kanzaki Kaori from A Certain Magical Index's light novel gradually warms up to Touma after he saves Index from having her memory reset by Neccessarius. She gets defrosted even further in the novels when Touma helps her get over her past.
Setsuna started as cold as ice due to seeing herself as a Failure Knight, but after the events of the Kyoto Arc, she opened up a lot more and became friendlier. Lampshaded by Evangeline during their match in the Mahora Festival Tournament Arc, where she told Setsuna to give up her newfound happiness because it made her boring and weak.
Princess Arika too. Flashbacks introduce her as a stoic and aloof princess, especially to Nagi, but she eventually fell in love with him. She ended up marrying him after he saved her from her execution.
Iceland is shown to be somewhat of a Deadpan Snarker, but he's described as a possible Sugar and Ice Personality in author's notes. Taking in consideration how he interacts with Sealand, it might not be THAT far from canon.
England, as well. He's harsh and bitchy, yes, but if he does care for you, he can be surprisingly tender once in a while.
Germany was frozen for a while as a result of not having any real friends. When he becomes friends with Italy he softens up a lot, although it's not obvious at first glance.
This is how a young Clare formed her relationship with Teresa of the Faint Smile. She initially opened up for entirely pragmatic reasons, because Clare was determined to stay with Teresa to the point of following her for two days straight, and if she died, Teresa would be implied in a possible murder.
Claire herself may fit the trope as well. She initially closed herself to Raki, but eventually let him know her true feelings for him, and stopping at nothing to protect him.
Mayu Miyuki is introduced as very much this, but almost immediately becomes a softer character when she meets Kaoru at school, and becomes much deeper and sympathetic when more of her Lonely Rich Kid backstory is revealed.
The tsundereishHarem Nanny Miyabi Kagurazaki is tsun-tsun to Kaoru and the rest of the cast at first, but shows more of her dere-dere side when she sees how kind they are to her and Aoi.
Bleach: Byakuya Kuchiki, the stereotypical Aloof Big Brother to Rukia who keeps his distance for decades as he wrestles with two conflicting vows (to never break the law, made to his dead parents and to protect Rukia, given to his dead wife, Rukia's sister). This comes to a head in the Soul Society arc when the law decides Rukia must be executed and he's forced to choose which of the two vows he upholds and which he'll break (in keeping with Confucian ideals, he chooses the vow to his parents over the vow to his wife). Once Ichigo resolves the conflict between Byakuya's vows, Byakuya mellows out, reinterprets his two vows in a more flexible way and in general starts becoming more openly warm towards everyone (although he still remains The Stoic on the surface... most of the time). It's still considered shocking when he jokes.
Hatori Sohma from Fruits Basket. Like the other cursed Sohmas, he was bound to obedience toward Akito, creating a cage-like feeling; as the Dragon of the Zodiac, he was actually one of the ones most affected. When Kana came into his life, she helped to defrost him, and they fell in love. Unfortunately, Akito traumatized Kana to the extent that Hatori had to erase her memory, and he froze his heart more than ever. He defrosted once more upon meeting Tohru (as expected), though to a somewhat lesser extent. It was even lampshaded with references to the snow and the spring that it preceded.
Aki Izayoi of Yu-Gi-Oh! 5Ds has her entire appearance in the first season based on this trope. It takes not just one but two duels against Yusei in order to completely thaw her out. (Apparently Defeat Means Friendship only managed to change her from emotionless to tearful the first time round.)
In Shakugan no Shana, Shana begins the series as an ice queen, cold, not caring for anyone. She sees herself as 'just a Flame Haze' and Yuji as 'just a Torch'. After some heartwarming from Yuji she comes to realize that he is more than just a torch and develops feelings for him when she sees a rival for his affections.
Double Subverted in Kara no Kyoukai. Shiki is an aloof girl with a rather misanthropic nature who doesn't want to relate to anybody. Mikiya tries to get close to her despite her many attempts to keep him away from her and eventually she starts to develop feelings for him. Unfortunately, those feelings are too much for her to handle and she tries to kill him with a knife and then throws herself in front of a car when she realizes she can't bring herself to kill him. But after she recovers from her coma, she starts to accept Mikiya more and he eventually becomes her Living Emotional Crutch.
The Pokémon anime's rendition of Mahogany Gym's Pryce. This was because as a young Trainer, he mistakenly thought that his Piloswine had deserted him after a battle they lost, when in reality it was frozen in ice and Pryce never found out. Once Ash and his friends help him resolve the HUGE misunderstanding and he finds his Piloswine again, Pryce cheers up noticeably. His manga rendition, even more so. This time, it's a Lapras that caused the sadness.
Sayo Mutou aka Magdaria from the Rurouni Kenshin anime is an embittered, sadIll Girl who keeps frosting up to anybody who doesn't belong to her Christian circle. In comes Sanosuke Sagara, who forces her to think and feel outside the box and made her rediscover the joy of living. Magdaria still dies, but at least she can go to Heaven with less regrets in her heart.
Inner Moka of Rosario + Vampire. She's fairly aware that this has happened to her and greatly dislikes it because, in her opinion, it has a negative effect on her fighting abilities. As of later chapters, she's also become a full blown Tsundere towards the protagonist, Tsukune. By the final chapter, she has completely defrosted into a sweet and cheerful cutie just like the now deceased Outer Moka.
Rei Ayanami goes from a seemingly emotionlessCreepy Child to realising that she does have feelings to a Sugar and Ice Personality over Shinji. The Rebuild of Evangelion movies take this a step further, even having Rei smile and act more open around Shinji. The other kids even remark how bizarre and seemingly out of character it is when Rei enters the classroom and says "Good morning" to everyone.
Initially, Asuka appears to be gearing for this in the original series, and, indeed, opens up a lot more to Shinji. Had she not gone into a deep depression after herMind Rape, she may have actually gone all the way with this trope.
Yuriko Star to a certain extent in The Irresponsible Captain Tylor. She starts off as being very by the book (since she's in the military) but eventually warms up to the dedicated slacker Tylor (who may or may not be a genius in disguise). It's lampshaded later on when she's transferred and someone under her command is surprised at how polite she is to her subordinates.
Sailor Mars in the Sailor Moon manga was easily this, although her character was a hot blooded and bossy Tsundere in the anime. In the anime, she defrosts specifically for Yuuichiro. Since he lives with her, but only starting in adolescence, it could be considered a late-in-life Childhood Friend Romance, or something
Kyoko Aoi from Future GPX Cyber Formula becomes this as the series progresses. It started showing signs of it when Shinjyo won his first championship, and comes in full-force when she saw Shinjyo and Kaga fighting and in Shinjyo's race in EP 6 of Zero.
Eureka from Eureka Seven. She went from an Emotionless Girl to an average emotional girl thanks to her lover Renton. Story-wise, this means Renton was "The One" for her.
Revy from Black Lagoon fits this trope well. Near the end of the series, we even see her playing with some kids. She was technically teaching them how to shoot people whilst playing, but still, no one actually got shot; which was a first for her.
Yukina from Watashi ni XX Shinasai! is slowly becoming as she experiences love for first time, but it's an extremely slow process.
In ...Virgin Love, Kaoru doesn't really like people until Daigo's warmer personality starts dethawing him. Even his subordinates notice he's become nicer, increasing his popularity at work.
Tiger & Bunny. Kotetsu spends a good deal of time trying to defrost his partner Barnaby - an icy, introverted, Ineffectual Loner. He finally starts making some progress after shielding Barnaby from enemy fire during a fight. But it's worth noting that Barnaby never changes his aloof, distant demeanour towards anyone other than Kotetsu even after being defrosted.
Oscar de Jarjayes from Rose of Versailles. She is never mean or snobbish, but she becomes more socially conscious and empathetic as the series progresses- due in part to her friends exposing her to the real world.
Used in Hyper Police since Poe seems to ignore Tommy's advances for the entire first half of the manga, turning a cold shoulder to him. Lampshaded by the fact that she actually is an elementalist controlling spirits of ice.
Casca from Berserk. While it wasn't his goal, Guts nonetheless accomplishes this when they got stranded together after a battle (during that time he learns about her backstory and he learns that they weren't so different) and he saved her life twice, turning Casca from a serious, aloof and cold young woman who hardly showed any affection other than for Griffith, to a softer, more sympathetic, and open person who is really just a girl who has a nicer, emotional sidethat she can't show due to her profession. And of course, that hate she had for Guts - turns to love!
Echo started out as Vincent's impassiveExtreme Doormat servant. Then, meeting Oz gave her the courage to defy her master and vent about how annoying he is at different intervals, and as more time passed, she eventually developed a Sugar and Ice Personality and generally started emoting more often.
Leo would coldly dismiss pretty much anyone who would try talking to him in the middle of reading and was also not very good with children. Meeting Elliot helped him overcome these, to the point that he is now able to call his fellow orphans his siblings. Although it seems like Elliot's death and his own responsibilities as Glen have refrosted him, though in adifferentmanner.
Imaizumi in Yowamushi Pedal after befriending Onoda. Even his teammates realize how uncharacteristically talkative Imaizumi is when he's with Onoda.
Princess Kinuko in Usagi Yojimbo seems to be a Rich Bitch to Usagi. After being attacked by ninjas and going on the lam, they eventually see that they're Not So Different, as she is nervous about going into an Arranged Marriage while Usagi is upset that his beloved Mariko has married his rival. They briefly contemplate running away together, but after they're rescued Kinuko decides to err on the side of duty and honor and the two part forever in a Bittersweet Ending. the whole story is a flashback sparked by Usagi hearing Kinuko's name as her entourage approaches. As it passes, Usagi wonders if she remembers him, and stares straight at Kinuko's palanquin while the rest of the townspeople have their heads down. When nothing happens, he accepts that she probably doesn't remember him anyway and walks away... just as Kinuko drops a chrysanthemum flower (her favorite flower) out of her palanquin door.
XXXenophile uses the trope rather literally in the "Orgasm Lass" story, describing the heroine's encounter with the Ice Queen. Orgasm Lass uses her power of generating orgasms to defrost the Ice Quuen (who is An Ice Person due to her super-frigidity) by focusing it on one area of her body at a time.
Starfire's evil sister from Teen Titans started to turn into this during the definitive Wolfman run. She proved herself to be a capable leader of her people and even started to put aside the needless, if somewhat understandable, grudge she bore against her sister. It didn't last.
Emma Frost is in no danger of defrosting completely anytime soon. Since she was already defrosting in the Generation X, but then Morrison reverted her to even more of an ice queen than when she was a villain), any defrosting now still seems like a regression. In Dark X-Men: The Confession #1, she's not only defrosting, she seems to be melting.
In the early years, Maggie Sawyer seemed to have a personal vendetta against Superman, often tried to arrest him as a vigilante. After Superman saved her from a terrorist plot, she began to warm up to him and eventually became a trusted ally.
This is how Jena Makarov progresses over the course of Nikolai Dante. At first, she is cold, aloof, and very much Vladimir's daughter. She starts to appreciate Nikolai when, after defeating Caius Zacharovitch in a duel, he says that Russia would be a far better place if Caius had been Jena's father, rather than just a father-figure.
My Little Pony Micro Series: Jade is initially very distant and rude towards Twilight, but Twilight's positive attitude and love of reading eventually brings them closer together.
Happens to Lumi the actual Snow Queen in the Fables Universe, in Fairest. She starts out cold-hearted and cruel, but quickly begins to change once she meets Ali-Baba. Turns out to be a partial subversion, as this is actually her slowly returning to her original personality from before she started working for Gepetto.
X-23: Abused, raised as a living weapon, quiet, withdrawn, and struggled to form emotional connections with others. Much of the focus of her solo series was Laura defrosting with the help of Gambit, Wolverine and Jubilee.
Nathanoraptor turns Abby Maitland from Primeval into one of these in Camp Scare. She is initially a snarky Jerk Ass towards the campers she is assigned to help, but eventually grows attached and fiercely protective of them.
Tangled Up In Blues has the romantic example with Taffy, who has had a bad experience with her previous love interest and Blues needs time and effort to make enough "cracks in her wall". Averted with Cherry, whom Blues tries but fails to defrost, much to his anguish.
Hiashi Hyuga in A Growing Affection goes from being distant and imperious in general, to being warm and supportive.
It is common in Naruto fanfictions to portray Kurenai and Yuugao as Ice Queens even though there was nothing to show this in the series.
A non-romantic example appears in the Hunger Games fanfiction Some Semblance of Meaning with Fen. At first, she is cold and distrustful toward Vale, but she warms up to her after she sees how much Vale cares about her district partner Kit, and later, how Vale tries to protect Fen's brother.
Fleur De Lis at the start of Of Lilies and Chestnuts. She shows nothing but apprehension towards potentially adopting Chestnut, a teenage bat pony. Once the bitterness from being infertile wears off, Chestnut starts to win Fleur over with her cheeriness and willingness to learn the high-class life.
Astrid is an Ice Queen via being both a battle-ready Action Girl and looking down at the protagonist as a useless, bumbling sap. She gets better, of course.
Toothless could count too, since he was wary of and didn't like Hiccup very much in the beginning. He eventually grew attached to Hiccup and become fiercely protective of him.
Tigress in the Kung Fu Panda series. Originally a bitter Resenter to Po who seemed to snatch away her dream of becoming the Dragon Warrior, she softens considerably after Po proves himself by defeating Tai Lung singlehandedly. By the time of Kung Fu Panda 2, she has become his closest friend among the Furious Five and perhaps even more.
Dr. Atsuko Chiba from Paprika. By the end of the film, she admits her secret crush on Tokita and opens up to him.
EVE from WALL•E initially doesn't want anything to do with WALL-E, but eventually warms up and falls in love with him.
Sgt. Calhoun in Wreck-It Ralph initially only sees Felix as an unplanned tagalong, but warms up to him throughout the movie and marries him at the end.
In Frozen, Elsa is emotionally reserved and afraid of her powers throughout the majority of the film, but after Anna sacrifices her life for her sister and almost dies, she understands that The Power of Love is what's needed for her to control her powers and thaw the winter she made.
So, a literal example, as Elsa is a Queen, with powers over Ice, who learns how to defrost her ice.
Many Bond girls, at least for the brief period before they melt into James' arms.
Vesper Lynd, Casino Royale. Technical realities of her being a civilian, and not actual royalty, while looking down her nose at the vulgar Bond are utterly meaningless, both in the story and in this trope.
Miranda Frost in Die Another Day appears to be a straight-up version of this trope, right down to her Meaningful Name, but is actually a subversion as she's secretly working for the villain, and thus didn't 'melt emotionally' as she appeared to.
Melina Havelock of For Your Eyes Only is arguably the iciest Bond girl, with her desire to avenge her murdered parents.
I ♥ Huckabees: The character Brad first appears to be a sexy, smug, condescending corporate manipulator. However, as the film moves to its denouement, it becomes clear that Brad is desperate to be liked — and convinced that being a male Stepford Smiler is the only way he can get people to like him. By the end of the film, the defrosting has already begun.
In Blade Runner, Rachael experiences a thaw after she discovers she's a replicant. Her confusion and vulnerability make the infamous Loving Force scene with Deckard all the more disturbing.
Back to the Future Part III, in which Doc, who in all likelihood has never been interested in a woman for all his many years due to his eccentric lifestyle and devotion to science, insists that love at first sight is a scientifically ridiculous concept - and is promptly proven wrong the moment he lays eyes on Clara.
Clint Eastwood's character in Gran Torino is a Defrosting Ice Queen. He starts off as a racist jerk with a short fuse but gradually throughout the movie warms to his 'gook' neighbors by seeing even more reprehensible characters elsewhere in the neighborhood.
Dr. Grace from Avatar. She's reportedly very cold and snarky until she gets to explore Pandora in person using an avatar, and then she becomes downright joyful. Of course, you'd be pissed-off too if the only way to get to the place you've been studying your whole life is because a bunch of army guys want to destroy it and its people for literal Unobtanium.
Neytiri could count as well, due to her being rather hostile toward Jake at first. She begins to warm up to him as they get to know one another, and eventually falls in love with him.
Tyler Perry makes use of this trope a lot. The heroines of Diary of a Mad Black Woman and Madea's Family Reunion, for example, have physical and sexual abuse in their backgrounds, respectively, and both require a tremendous amount of care and patience from their eventual love interests before they finally thaw.
In Pride and Prejudice, both Darcy and Elizabeth are ice princesses; they go back and forth rejecting each others advances until the end of the last act where Elizabeth finally accepts Darcys hand in marriage after he proposes for a second time. Probably belongs in literature as well.
Practically the entire point of The Cutting Edge, which is about an Olympic-class female figure skater who can't find a partner because of how high her standards are and how vicious she is toward them. The guy she eventually finds actually refers to her as an ice queen in the scene right before she finally defrosts. It's so much in focus that the film even ends before we find out whether or not they won the Olympic gold medal.
Sally from Don't be Afraid of the Dark starts out as this. When she first meets her dad's new girlfriend Kim, she coldly rejects Kim's attempts at friendship with her, first shown when she hesitantly accepts the teddy bear Kim bought her. Over the course of the film, she warms up to Kim when the latter is the only one to believe her stories about the evil creatures living in the old mansion they're staying in. This is best exemplified when she's shown to be visibly upset when the creatures ruin her teddy bear, and even more so when she cries at Kim's Heroic Sacrifice near the end.
A strange variation where, rather than over the course of Iron Man 2, on the in-movie film reels Tony is going through, he starts to find more and more evidence that his father was not always the cold fish he remembers from his childhood. (This was paid off in the Captain America film.)
Howard Stark: Ladies and gentlemen, I'd like to show you...my ass. *turns his back on the camera and thrusts his butt out*
The emperor thinks this is what his wife is in Legend Of The Black Scorpion, even telling her if she is a lump of ice, she will melt in his mouth. Averted throughout as he's wrong and he fails.
Hortense for Gilbert in Small Island. He considers it a major milestone when she deigns to laugh at one of his jokes.
Maid Marian in some versions of the Robin Hood legend.
A very literal example of this can be found in the fairy tale Heart of Ice. In this tale, a young man goes on a quest to defrost a young princess's heart, without which he can only be friends.
There is a non-sexual example of the trope in the fairy tale The Snow Queen, where the titular character freezes the heart of a young boy, making him Not Himself, until he is defrosted by his sister's love.
Except in some versions where it doesn't work, he freezes completely, and she goes home and forgets about him.
In the original, it's his childhood friend Gerda, not his sister, who attempts to rescue him, and she succeeds.
Calling Perry Rhodan "literature" seems inappropriate but his love interest, the icily beautiful and scornful Thora of Arkon definitely qualifies for this trope — she ends up his devoted wife.
Rachel in No More Dead Dogs. She initially thinks that Wallace is a dumb jock, but warms up to him later and by the end, a letter from a Genre Savvy Julia Roberts tells her that she's practically fallen for him.
Played with in Twilight. Rosalie Hale looks like she's warming up to Bella, but it's only because Bella's pregnant, which Rosalie can never be.
Myn Donos, also a Wraith, is a male version. He'd once been in charge of a squadron of his own, but everyone except him and his astromech was killed on their first mission, and he blamed himself and became the Wraiths' Cold Sniper, going into a catatonic Heroic BSOD after that astromech was destroyed and his failure became complete. His wingmates brought him out of it, particularly a woman who'd started falling for him. When she died, he was left a little less cold, and Lara did the rest.
After more than twenty years of suffer, Cassie from Uncle Tom's Cabin is pretty much a cynical wreck of a Broken Bird. She's harsh and snarky towards Tom and Emmeline when they arrive and talks back to her owner Simon Legree and is feared by almost everyone... but as time goes by, Tom's friendship warms her up slightly, at least enough to take Emmeline with her and run away from the manse. Which, unbeknownst to her, would trigger Tom's Heroic Sacrifice.
Much of the plot of The Queen of Attolia revolves around the titular queen slowly defrosting, ending with her marrying the hero, Eugenides. The King Of Attolia shows her continuing to defrost, which disturbs most of the kingdom, which is used to her being cold and cruel.
Skirlet Hutsenreither plays this role in Jack Vance's book Night Lamp - over the course of the story, she goes from a stuck up Clam Muffin (it's a social caste) to a warm and friendly space traveler, largely because of Jaro Fath, the main character. (Almost all of Vance's heroines are this, at least towards the hero.)
Bean, in the Ender's Shadow series; particularly Shadow of the Hegemon and Shadow of the Giant. In Ender's Shadow, Bean was a snarky, cold calculating little boy who was extremely logical and restrained. By the end of the series, having found love, he's happy, romantic, and emotional.
Sofia Mendes in The Sparrow. Tragically, the sequel Children of God shows her not only refrosting, but becoming a Knight Templar.
The novelization of the original Alien vs. Predator comic arc does a more thorough defrosting of Ice Queen Machiko Noguchi. She was so unintentionally aloof from the colonists under her authority that she was dubbed the "Nitrogen Queen" behind her back. Only three months into her stay does she realize that they all hate her, and immediately sets about changing her status among them. She makes decent but slow headway until the Predators begin hunting colonists and the subsequent outbreak of Aliens, at which point she becomes a BadassAction Girl and repeatedly risks her life for all of them.
Aunt Polly from Pollyanna is an unromantic example. She begins the book as cold and borderline cruel but Pollyanna eventually defrosts her however it's not until Pollyanna's badly injured that she completely defrosts.
Ex-Heroes has an excellent example with Stealth and the Mighty Dragon.
Richard causes this in the Sword of Truth series just by being. The Mord-Sith, Sisters of the Light, and Nicci, all of whom are some of the iciest queens out there.
Sherlock Holmes becomes this towards Watson; especially shown when Watson gets hurt.
While the titular character of Beachwalker is a kind and giving person, it takes a bullet wound for her to let anyone start to get close to her.
Glinda Arduenna Upland in Wicked becomes this as her friendship with Elphaba grows, and even more so when Dr. Dillamond was killed by Madame Morrible
In A Brother's Price, after the disastrous marriage to Keifer Porter, the Queens have decreed that their daughters can only get married if all of the surviving ones of age agree to it. Thanks to Keifer, Trini is extremely standoffish towards the man her sisters favor, agreeing only because otherwise the Porters will buy him and she hates that family, but she warms to him gradually.
Angel from Redeeming Love is deeply embittered and cynical as a result of a lifetime of forced prostitution; the novel’s main premise is one man’s divinely-appointed attempt to reverse these effects via The Power of Love. He is ultimately successful, though he strays heavily into Love Martyr territory in the process.
The Mortal Instruments: Like her brother, Isabelle is not very fond of Clary at first. Later, though, she begins to open up to her.
The Heralds Of Valdemar: In The Black Gryphon, Winterhart is a healer who views her gryphon charges as things and is utterly cold and emotionless to humans. She seeks out the services of the kestra'chern Amberdrake for persistent back pain, but over many weeks, Amberdrake slowly and laboriously gets her to open up, first by showing her that the gryphons are sapient beings with feelings, then by delving into her past. It turns out that she was a child of nobility who was in the High King's court when the evil mage Ma'ar attacked it with an Emotion Bomb. As she was also an undiscovered empath, the fear induced by the bomb inflicted particular damage on her pysche, which she covered up by retreating into a shell of uncaring. This revelation allows her to finally start healing, and in the aftermath she also takes Amberdrake as her lover.
Janine and Candayce, in Dinoverse, both go through this over the course of having to escape the Cretaceous. They go from enemies to, well, frenemies sniping at each other with a minimum of actual malice. When they go home Janine reconnects with her mother and stops rebelling so much, Candayce stops being such an Alpha Bitch, starts volunteering, and begins to date the geeky nerd who was in love with her.
Melissa "Schoolmarm From Hell" Mailey, from Eric Flint's 1632 series, finds her notoriously aloof, acerbic self softening considerably due to a combination of falling in love and being thrust three hundred and fifty years or so into the past. The former has the expected effect, but the latter forces her to really confront her own principles and what they mean in the context of 17th century Germany. And she becomes something of a mother figure and counselor to many of the young women stranded by the Ring of Fire. All combined, the Melissa Mailey who emerges is altogether a much softer and more approachable figure... at least to anyone who doesn't get on her bad side. Like setting the Globe Theatre ablaze, for instance...
Margaret "Hot Lips" Houlihan on M*A*S*H. During the series' early "comedy" years, she started as a bossy, unlikeable bitch of a head nurse. She had many defrosting moments (mostly with the laid-back Hawkeye) after the first season, but her first defrosting episode was "The Nurses", and since, due to trouble with men like Frank Burns and Donald Penobscot, although she's still a hard-nose (she is an Army major, after all), she comes off as a significantly more likeable character.
Glee: Kurt, especially after his transfer to Dalton means he no longer needs to be constantly on the defensive just to survive high school. And he is indeed a queen...
Cordelia Chase from Buffy and Angel starts out as the definition of this trope (especially towards Xander and Doyle on the respective shows) and by the end of the series has evolved into a warm caring woman.
Star Trek: The Original Series: Spock's relationship with Kirk is a platonic example of this. Although it takes years for Spock to fully accept that emotions are a good thing, most of his moments in between are due to the captain.
Kirk also defrosts a haughty monarch in "Elaan of Troyius."
Star Trek: Deep Space Nine: Odo tried very hard to remain the dispassionate observer of humanoid behaviour but he found himself making friends despite himself.... friends that were determined to make him enjoy having friends. Friends that won this battle in the long run.
In an interesting case of a role defrosting an actor, the title role on Murphy Brown did a lot to soften up Candice Bergen's image after years of being known as a cool debutante. Her dry wit has been a staple of most of her roles since.
Sherlock in BBC's Sherlock over the first two seasons. Although not without bumps along the way, his friendship with John helps Sherlock slowly learn to open up to the other people in his life (albeit in an eccentric, clumsy way) to the point where his priorities at the end of the second season are wildly different from those in the pilot, or even the end of the first season.
Sarah Jane Smith of The Sarah Jane Adventures started out "positively frosty!" - and can you blame the woman, considering aliens are out to kill her? - but softened considerably after meeting Maria and adopting Luke. Later she goes on to say that Luke gave her something to live for.
Ashley Jeurgens from The Secret Life of the American Teenager. Started out being the down-to-earth girl who said won't repeat Amy's mistakes, being the voice of reason and trying her best to be a good daughter to her almost crumbling family. Now, she might be steps away from being almost like Amy...
In Dance Academy, Abigail is initially quite a horrible person, but Sammy's persistence and support of her eventually makes her much nicer and she eventually falls in love with him despite her claims that she "[doesn't] do emotions." Christian starts off very cold and distant from everyone and isn't too keen to make friends. Tara, Kat and, again, Sammy all play a role in making him a warmer person.
Marguerite in Sir Arthur Conan Doyle's The Lost World. In the beginning she appears cold and uncaring. She is perfectly willing to sell Veronica for a way home of the Plateau and usually seems to not care about any of the others. And then one looks closer. She grows to care about the others a lot. When Summerlee gets stung by a gigantic bee and hallucinates about his dead wife she resumes that role to comfort him, she looks out for Malone and Veronica, helps Challenger and becomes Roxton's confidante whenever the memory of his brother breaks him. But although she learns to trust every expedition member with her life she's still careful about letting them know about her past and why she really came to the Plateau.
Dana Scully of The X-Files is this way. She is naturally steely and emotionally distant to everyone, but especially to Mulder in the early seasons. Eventually, he breaks through and she develops a Sugar and Ice Personality, in which she remains cool and distant to everyone else, and a little bit freer with her feelings with Mulder.
Althought the defrosting is only partial, Alex in Wizards of Waverly Place could be considered a example, either throught Jalex,Dalex or Malex.
Lady Mary Crawley of Downton Abbey slowly but surely defrosts over the course of the first two seasons thanks to the influence of Matthew. She evolves from someone utterly selfish whose only concern upon her unofficial fiance's death is how long she has to wear black, to a woman who realizes her own mistakes and eventually admits them to those she loves. She even outright states that Matthew sees her as a much softer person than others do. After Matthew's untimely death, Mary reverts temporarily to her icy ways.
One interpretation of Matchbox 20's "If You're Gone" is a husband undergoing this trope.
Willy, in the song "Eppie Morrie," clearly thinks this is what he is doing with the title character, but it comes off as more a Stalker with a Crush. After she refuses to marry him, he kidnaps her, forces a priest to marry them at gunpoint, and then tries to consummate the marriage. Eppie Morrie successfully fights him off, and in the morning demands to be returned to her mother just as much an ice queen (and a maiden) as she was when the whole thing started.
In the 1940s standard "(I'd Like to Get You on a) Slow Boat to China", invoking this trope is the singer's motivation for taking the boat trip.
Out on the ocean, far from all the commotion, melting your heart of stone...
Older Than Print: In Norse Mythology, the god Freyr fell in love with the giantess Gerðr who first rejected him but eventually gave in to his persuasion and returned his love.
The Russian tale of Snegurochka has a maiden of literal snow whose melting heart kills her.
The title character of Puccini's operaTurandot, after a Forceful Kiss. Except probably because Puccini died before he could finish the last act, the defrosting feels rather unconvincing.
The title character of Gilbert and Sullivan's Princess Ida is a strong, educated woman, who has forsworn all men (largely because all the men in her family are either nasty sarcastic buggers or utter idiots). The plot throws her in with the man she had been married to at birth, who is disguised as a woman for most of it. It parodies a poem by Tennyson, and does have some unfortunate Victorian values in it, but better than a lot of portrayals of the time.
Metal Gear Solid's Solid Snake goes from gruffly agonising about the battlefield and trying to avoid revealing he's falling in love to making speeches about love and how beautiful caribou are. He's not quite as sappy in his later appearances, but much more emotionally-open and compassionate than he was at the start.
Played with quite a bit in MGS3, where Naked Snake/Big Boss spends most of the game stubbornly refusing to play along with EVA's advances on him, often in quite tragic ways, particularly when at one point, EVA kisses him passionately, and Snake simply stands there, with a hollow, yet sad expression on his face, as if he is incapable of feeling any form of attachment. It gets interesting when Snake finally warms up to EVA, and it seems they may in fact live Happily Ever After, but in reality, EVA was playing Snake from the beginning, and would have killed him, were it not for the Boss asking her to tell Snake the truth. The result is not only the re icing of his heart, but the beginning of his descent into villainy as Big Boss.
And Tokimeki Memorial 2 has Kaori Yae, who's a Broken Bird like Mira, albeit for different reasons : she was betrayed by her friends of the Volley-Ball Club she was a member of in her former High School, who abandoned her after she Took The Heat in order to save the club from a scandal. She'll need a considerable ammount of The Power of Love from the protagonist to heal the scars in her heart and make her turn back to her former Genki Girl self. No wonder she's the Ensemble Dark Horse of this game.
Demon Princess Rozalin from Disgaea 2: Cursed Memories. A partial subversion of the standard-issue Fairytale princess with an unbearably arrogant (and murderous) attitude - and a hand-held gatling-gun. It's downright impressive how many chapters she lasted before falling into the arms of the handsome, red-headed, fist-fighting hero, really....
Rouge the Bat is the Sonic the Hedgehog series' representative of this. Beginning as a villainous jewel thief who wanted to acquire the Master Emerald for herself, seemingly unconcerned about its powers to stop evil acts in the right hands, the plot later reveals her to be a government agent, although she still steals jewels on the side, and the government itself is depicted as less than pure in Sonic games, and she seems to discover the value of friendship eventually. Perhaps it is Shadow's act of rescuing her from death in a base that self-destructs that opens her mind to this, as she becomes fairly loyal to him in subsequent games, returning the favor multiple times. She also gives Knuckles back the Master Emerald after he saves her life, and it is suggested that they fall in love; they nearly kiss, though both stop and quickly hide their emotions. Knuckles claims he was just trying to save the Master Emerald; Rouge is sour-grapes about it.
Blaze is another good example. Initially, she's extremely seclusive and chilly. She believes that she has to do everything by herself, and reacts with anger and confusion when the other characters suggest she get Sonic's help. This is best shown when, at the halfway point of Rush, she forces Sonic to fight her to see who should go after Eggman. By the end however, she's grown more friendly and open, mainly due to Cream's encouragement.
Celes Chere in Final Fantasy VI is cold and unfriendly towards the rest of the cast for quite a while. On the way to the battle of Narshe, Celes proclaims that she's not just some love-starved twit and Edgar himself says that she's cold as ice. The person that defrosts Celes is Locke. Celes slowly falls in love with Locke and realizing that he's still alive despite The End of the World as We Know It is what motivates her to Putting the Band Back Together.
Cloud from Final Fantasy VII fits this trope primarily toward Tifa, though his negative reaction is due to a truly epic and widely applied inferiority complex.
The defrosting of Squall Leonhart in Final Fantasy VIII makes up most of that game's plot.
Lulu in Final Fantasy X begins the game as, for the lack of a better word, cold-hearted, cynical bitch. She's constantly annoyed at everything and berates Wakka for being an irresponsible and naive idiot, who never thinks anything through and refuses to face reality, and has nothing but pure contept for Tidus, whom she (mostly rightfully) regards as the escaped loony who is Too Dumb to Live. She only tolerates Tidus's presence, because Yuna requested it and she never asks for anything that isn't really important to her. It's only after Tidus, in all his naivity, starts asking questions nobody else has ever asked before, that she begins warming up to him, and at least starts to respect him for his endless optimism that motivates everyone to keep going. (Though he actually just was the only one who didn't have the slightest clue what their quest was really about.)
Mitsuru Kirijo from Shin Megami Tensei: Persona 3. Although she's the Ojou instead of a Rich Bitch, she doesn't seem very adept in social situations and has a few trust issues, namely withholding key information on the origin of the Shadow threat from her teammates until confronted by one of them. She begins to warm up to the party after her father, who had been her primary reason for fighting, is shot dead in front of her and Yukari snaps her out of her subsequent depression. Right around this when the Protagonist can start a relationship if intelligent enough and is when we can see her soft side.
Ice Witch/Queen Blanc Neige from Shining Tears definitely count. Frequently partnering with her will make her actually lessen her haughty attitude and smiles for the first time, if you can hook up with her.
Soren from Fire Emblem Tellius would qualify as a male example, even if a portion of said defrosting occurs during timeskip. Notable in that gender roles aren't actually reversed; the cause of the defrosting is the male protagonist. I'm sure you can see where this is going. It's even commented on by The Empath, ice around the heart melting and all.
Micaiah: (to Soren) Your heart is frozen, but I feel a warm core trying to melt through that ice. I see... You have someone you cherish very much. Someone you rely on.
Fire Emblem has another male example in Jaffar, thanks to the influence of his best friend (and possible love interest through supports) Nino.
Aribeth in Neverwinter Nights is not so much icy as very professional and unwilling to discuss anything outside of the mission in the first chapter. Later events crack her shell enough that she will fall for a male player character.
Nathyrra in Neverwinter Nights: Hordes of the Underdark is rather sarcastic in response to the player's early flirtations but warms up gradually through the third chapter.
Bastila Shan from Knights of the Old Republic, though when she notices she is defrosting she panics and freezes solid again (since Jedi are supposed to abstain from romantic relationships) until the endgame. Best stated by HK-47:
Mockery:(in Bastila's voice) Oh, master, I love you, but I hate all you stand for, but I think we should go press our slimy, mucus-covered lips together in the cargo hold!
The Handmaiden from the sequel. She won't even tell you her name for quite a while (it's Brianna).
Miranda Lawson in Mass Effect 2, particularly if the player pursues a romance with her and completes her loyalty quest. The defrosting itself is a little more subtle than usual, with most of the change coming from the inflection on her lines and the random interactions with other squadmates. By Mass Effect 3, she's completely defrosted.
Especially Kasumi's comment on how strange it is to see Miranda smiling.
Or Liara's comment that Shepard has no idea how much he's changed her.
Jack in Mass Effect 2 is an inverse example; her romance arc consists of getting her to calm down and (in Liara's words) give her faith in something besides anger.
Morrigan in Dragon Age: Origins. She begins the story as an arrogant, ruthlessly pragmatic witch with a "survival of the fittest" mentality. She has a low opinion of friendship, and an even lower one of love. Treat her well, however, and she warms to the protagonist a great deal, becoming a male protagonist's lover, or a close friend to one of either gender. She remains callous towards most people, but comes to like the protagonist to a degree that makes her uncomfortable.
Thanks to the tidbits about her past revealed in Castlevania Judgment, we can now safely assume that Sypha Belnades is a version of this. Before even meeting Trevor Belmont (her future husband), she is known to be a character who would attack those who wield dark powers, regardless of their heart (she attacked Cornell for just being a werewolf, and Shanoa for wielding the Glyph, which has dark powers), and coming off a bit bitchy, due to a very troubled past (she and her kin were persecuted for how long we do not know). In the end of her story in Castlevania III: Dracula's Curse, however, it is implied that she has learned to find happiness thanks to Trevor.
Also arguably on Lamia Loveless (considering Signum from above is an Expy of her), being a robotic example. She starts out as a complete cold soldier and efficient spy who pretty much only cares about fulfilling her mission, without much care about life, especially her own. Further interaction with the good guys, however, made her learn to value life and be more open to emotion thus learning what it feels to be human.
Tear Grants from Tales of the Abyss who eventually warms up to Luke and ends up whispering that she loves him just before he goes off to free Lorelei at the end.
Midna in The Legend of Zelda: Twilight Princess definitely goes through this process. At first, she teams up with Link because they have a common enemy, but by the end she genuinely cares for him (and Zelda). So much so that she uses a tear to shatter the Mirror of Twilight and protect Hyrule from its evil influence.
In fact, it's amazing at how this works alongside her animations. One of Midna's idle animations while as Wolf Link is to pat him on the sides in a sort of "Giddy up" motion. At the beginning of the game, it comes off looking extremely humiliating and condescending. At the end, it seems beautifully playful and friendly. There is zero change to the animation at all, it's all character perception.
There's also Tetra in The Legend of Zelda: The Wind Waker. Especially after her true importance to the plot is revealed and she realizes that she can't just act as the selfish pirate captain anymore.
Irene of The Legend of Zelda: A Link Between Worlds initially only helps Link to avoid the danger that a fortune says will happen to her if she doesn't "take care of green," and is openly resentful toward Link for the inconvenience it brings her. But when you talk to her grandmother after she gets kidnapped, you find that she considers Link a friend. When you rescue her, she is reluctantly grateful, and she also expresses concern about Zelda and her grandmother.
Miranda in Happy Salvage is introduced as a cold, selfish maverick that doesn't need anyone's help that wants to cheat you out of any profits you make from your dives. She warms up fairly quickly. All this BEFORE you find out not only does she have a sick little brother but the siblings are also orphaned children of a pirate father that was betrayed by his own comrades. Let the healing begin.
Zhores from Absolute Obedience is a rarer male example. His code name is the Ice Queen, even. By the time Louise is done with him, there are explicit in-game metaphors to him melting, and becoming sweet and warm.
King Graham in King's Quest V defrosts a literal ice queen by playing a tune on his harp.
Aoba in Family Project. Oddly enough, it's actually in her own route that she gets the most jerkassy and cold before melting. However, in all routes she does warm up to them quite a little... making her a tsundere. Better than nothing.
Nick from Left 4 Dead 2 acts this way in the beginning. The only thing he believes he has in common with the other survivors is they they are caught up in the zombie outbreak together. He planned to quickly ditch the survivors as soon as he could and he even degrades them occasionally, such as calling Jimmy Gibbs Jr. (Coach and Ellis' hero in stock car racing) an asshole or making fun of Ellis' accent and branding him with the stereotype of southerners ("You can almost call this the cement river, Ellis!"). As the survivors progress in the campaigns, Nick starts to warm up to them, though is still sarcastic most of the time. When Ellis dies, Nick softens up even further by saying "Remember all those things I said about you, Ellis? I was only joking..."
Fatima from Luminous Arc 2 if the player choose the correct dialogue choice of trying to understand her, instead of siding with the rest of the Witches. Noticeable moments of defrosting is during her Intermissions, as well as Fatima route only events: Master Mattias's grave and the Final Bond.
Master Chief from Halo who is depicted in the first game and novel as being a Stoicman of few words willing to do whatever it takes to complete the mission. By the end of the third game Cortana has helped him regain a little of his humanity, also due to him losing so much During the War. Shares emotional moments when rescuing Cortana and holding Sgt. Johnson as he dies.
And, in Halo 4, when Cortana sacrifices herself in the last level, not even the Chief is immune from yelling her name as he realises what she's about to do. Then again, between Johnson, Keyes and the countless Marines, Cortana was the last remaining entity willing to stick with him through thick and thin (albeit not having much choice in the matter).
Selena from Harvest Moon: Tree of Tranquility (and Animal Parade). At low friendship levels, she'll say things like "I dislike chatty people", but she defrosts into a very happy and caring woman. Sadly, many people see her low-heart quotes and think "Oh, Rich Bitch"...
Reina from Tale of Two Towns is a minor example. She's very reserved and focused on her work, and she admits she sometimes prefers the company of plants to people, but if you manage to court her properly...
You can do this in Animal Crossing: Wild World with Sable and Brewster by visiting them every day.
Gwen from Guild Wars takes some defrosting before she warms up to her love interest.
Princess Elika in Prince of Persia (2008). She initially is put-off by his cocky and flirty demeanor, but eventually warms up to the Jerk with a Heart of Gold. Helps when that guy is helping you save your land from an evil power even if he barely knows you.
Patroklos in Soul Calibur V starts of as extremely cocky to the point where he kills a man because he believes to be Malfested. As the story goes on, he is not that kind of a person anymore.
Kainé of Nier starts out aggressive, cold and mistrustful of the others, but starts to warm up to them after they save her life, joins the party, treats Emil like a brother and eventually falls in love with Nier.
Dark Souls has Rhea and Quelana. Rhea is an uptight princess who warms up to the player after rescuing her after her companions all either betrayer her or died, leaving her trapped in a pitch black cave filled with dangerous monsters. Quelana is one of the Daughters of Chaos, the children of the Witch of Izalith. After her mother and sisters where horribly corrupted after a failed experiment, Quelana became a Broken Bird who eventually warms up the to the player after they prove their skill with pyromancy and by ending her mother's suffering.
Adrian Andrews in Phoenix Wright: Ace Attorney: Justice for All. She is smart, calculating, and is pretty much straight to the point. She doesn't like to waste time with trifling details and will shut you down if you try to talk to her about topics that don't get her attention. However, all of this is just a mask. She only acts cold because she is pretending to be tough and independent. Celeste Inpax, her mentor, was her strength and when she committed suicide, Adrian tried to do the same as well. Her cold demeanor is to hide the fact that she can't live on without depending on other people. By Trials and Tribulations, she is a much more cheery person.
Also Lana Skye in in the Bonus case of the first game. When Phoenix first meets her, she seems devoid of emotion, but once the case has been won, she can smile at last. The reason for her behavior is because Gant blackmailed her into becoming Chief Prosecutor and assisting with his schemes in order to avoid having Ema be suspected of Neil Marshall's murder, and Lana became cold in order to endure doing illegal things fo him.
Franziska Von Karma, of all people, begins warming up a bit in Trials and Tribulations during the time when Maya is missing.
Miles Edgeworth would count, also. He's cold and rude towards everyone, even when Wright becomes his lawyer in 1-4 and believes in his innocence the whole time. He begins to show emotion during his trial, where his LIP TREMBLES after Maya gets held in contempt of court to save the case and he gets persuaded to show his happiness for being acquitted in an extremely awkward shout.
By her own admission, Tomoyo Sakagami from CLANNAD starts out as this... in flashbacks. Due to a screwed up family, she could only vent her anger by fighting and hurting other people (somehow attaining a legendary delinquent status), and distances herself from her family, even her slight Morality Pet of a little brother. When her parents tried to divorce, she couldn't have cared less. After her brother cripples himself by jumping off a bridge into a river (jumping in front of a moving car in the Visual Novel), she and her family make amends to each other and Tomoyo defrosts into someone much warmer... which is the Tomoyo we see in the beginning of the series.
Komachi Tsugumi in Ever17 starts out as a total Jerk Ass who always seems to look down on the others. However, she eventually warms up to the others and even falls in love with Takeshi and bears his children only to be frozen again again after she believes Takameshi dead and has her children taken away, and then defrosted for good in the True ending.
Subverted in Umineko no Naku Koro ni. A large part of episode 3 of the visual novel focuses on Beatrice realizing how cruelly she has been abusing her powers until that point. She reforms, eventually even helping the Ushiromiya side of the game board, and ends up denying witches to have Battler win the game, causing her own demise. At the very end of episode 3, all of this is revealed to only be an act to get Battler to voluntarily recognize the existence of witches, and Battler almost signs a contract to do so until he is interrupted by the unexpected visitor Ange, who explains to him that he has been tricked.
In Grisaia No Kajitsu Yumiko starts off attacking the protagonist with a switchblade but eventually mellows out in her route.
An interesting example is Octavia from Tears to Tiara. She starts as more of an Emotionless Girl, and is defrosted not by the hero (though he does play a role), but by the hero's childhood friend Morgan. Hello Les Yay! Later in the series, Octavia and Morgan become quite close and Octavia matures into a Lady of War.
Ryoma Shirasagi in Office Secrets is the protagonist's immediate supervisor in her new job, and he's an incredibly demanding perfectionist who can barely say anything to anyone without including some kind of criticism. As his route progresses and the protagonist gets to know him, however, she sees him demonstrate quite a bit of kindness in understated ways, and late in the route there are a few moments in which his rigid self-control breaks completely.
For Shanna Cochran in Fans!! it's not so much her heart that needs defrosting as her imagination. Partly owing to her Back Story (insane mother, father who abandoned her), she's so determined to be "normal" that she's suppressed her sense of fun and wonder to the degree that she's grown up to be uptight, unimaginative and hopelessly mundane. As well as her continued exposure to her friends in the Science Fiction club and the various weird things she encounters, her imagination is freed further by a series of psychological tortures she is put through over the course of the strip which, although designed to break her, ironically only serve to make her stronger by allowing her to free her imagination and outwit her captors. The romantic angle is not entirely absent, of course, since this also has the beneficial side-effect of warming her heart as well; she gradually falls in love with Will, who eventually returns her feelings, after which Shanna is able to help him overcome his own tragic childhood.
Due to her unusual upbringing and the death of her mother, Annie from Gunnerkrigg Court starts off as a Spock Speaking killjoy, unable to communicate comfortably with her peers and oddly passive-aggressive towards those older than her. Mostly due to her best friend Kat she's gradually moved away from this, to the point where it's unusual for her not to be smiling.
Carrie from Loserz. Considering that strip hasn't been updated in two years now, and there's been no word from the creator since — she'll probably never finish any such journey.
Penny in early strips, describes herself as "too pretty to share any feelings with the likes of you" and, despite her popularity, keeps boys and even her girl friends at arm's length. She begins to open up in stages when she falls in love with "bad boy" Rich, supports her best friend Sara as she comes out and most of all during "The Popsicle War" when, after losing all her friends due to Karen's gang's machinations, overcomes her rivalry with Aggie and works with her to stop Karen and win her friends back. She now shows her feelings, positive and otherwise, much more readily.
Double Subverted in regards to Charlotte. She's introduced as nutty, cold and eager to "punish" whomever she thought deserved it, but her interaction with Duane showed her getting mellower... Until The Stinger of the second chapter of the Missing Person arc reveals that she is the one who kidnapped Cyndi. But in the third chapter her motivation for doing so is implied to be related to Cyndi's actions hurting others, especially Duane, and Charlotte tells him that she is a better person for having met him.
A variation in Red vs. Blue with Agent Carolina as we're introduced to her in Season 9 during the prequel Freelancer scenes where she's generally nice and supportive of her team (if a tad hypercompetitive). At the end of Season 9 and into Season 10, we meet her in the present and she's gone completely into heartless ice queen territory. Then comes Season 10, Episode 12 when she is shown journal entries of her late love interest and let the thawing commence.
Cornelia Hale is a pretty good example, starting out as rather hostile even to her own friends, she softens up a bit once she hooks up with Badass Normal Caleb in the second season. The original comic version of Cornelia wasn't quite as bad. The comic version of Cornelia had a lot of traits too; but in a more The Spock way than her Valley Girl persona in the show.
Orube, however, really is a good example of this in the comics, beginning as a rather typical emotionless warrior woman-type and ending up being an older sister of sorts to the main characters, and falling in love with resident Ineffectual Sympathetic Villain Cedric.
In the first season (especially the first episode) of Drawn Together, it looks like Princess Clara will go this way. Ultimately, however, they end up taking her in the other direction.
Even though she has few lines in Justice League, the female Dr. Light fits this. Her reaction to Amanda Waller's announcement that Ace will soon die of an aneurysm? "Problem solved, then." Waller, no slouch in the Ice Queen department herself, quickly disabuses her of this notion.
Cheerleader Liz Allan from The Spectacular Spider-ManAnimated Series shows signs of doing this; she is kind and encouraging to Peter, but immediately turns into the Alpha Bitch around the Jerk Jock Flash... and she looks like she regrets the quasi Face-Heel Turn. By mid-season, she's pretty much completely defrosted, having broken up with Flash and directly expressed interest in Peter. Of course, given this huge amount of Character Development, when compared with her mainstream comics counterpart, Peter actually comes off as something of an unintentional Jerk Ass when he breaks up with her to be with Gwen. She attempts to cover the whole thing up by making a huge scene and implying she is doing the dumping in front of a crowd, but then later is seen hiding behind a corner, crying her eyes out, showing that she genuinely did have feelings for Peter.
This gradually happens with Sissi from Code Lyoko, in spite of the Reset Button complicating it. In the last episode of the series, she even becomes an official friend of the protagonists.
Raven in Teen Titans gradually warms up to her True Companions. It culminates in the fourth season, where she's all but shed every emotional barrier that she'd ever thrown up between herself and the other Titans by the end of the battle with Trigon.
Toph takes a while to warm up to any of the heroes, and has to adjust to the cooperation expected in a group of equals. She never gets any less sarcastic or self-reliant, but she learns to trust and confide more. Somewhere along the line she develops a crush on Sokka (despite knowing he's already got a girlfriend), who up to that point had been the most frequent target of her snarking and pranks. Marking her as a true, old-school Tsundere, he continues to be the most frequent target of her snarking and pranks, while she keeps her affection totally secret. She shows similar affection toward Zuko toward the finale, indicating that Sokka isn't that unique a case for Toph (though her crush on Zuko most likely ends after spending "the worst field trip ever" with him).
Zuko too, of the Jerk Ass variety. He has a soft, dorky center that he only shows when he's around Mai and/or Team Avatar.
Mai likewise can get pretty mushy around Zuko, despite being the Emotionless Girlanywhere else.
Happens twice in The Fairly Oddparents. In "Snow Bound" Timmy gets Locked in a Freezer with Vicky, and the two become friends...until the end of the episode, where Vicky reverts to normal. Then, In the "Wishology" trilogy, both Vicky and Trixie express sadness after Timmy's heroic sacrifice, indicating they're beginning to see him in a new light. This only results in anotherReset Button, this time in the form of Laser-Guided Amnesia
Ben becomes a non-romantic example in Ben 10: Omniverse; when assigned a new alien Naive But Skilled partner named Rook, he is initially unwilling to accept and would rather work alone; as the story goes on, however, he does befriends it. He actually lampshades it in the form of Rath in "It Was Them".
Blackarachnia in Transformers: Beast Wars pulls this off perfectly - she starts off being confused that Silverbolt is unwilling to hurt her for being female, then moves on to exploiting his 'weakness', before finally accepting it.
June from KaBlam! was usually a bit of a Jerk Ass, but in season four, it's noted that she's stopped teasing Henry and is a much nicer person than she used to be.
Kiva from Megas XLR shows signs of this. In the pilot, she's barely able to hold back her contempt of both Coop, Jamie and most of our "modern" society, deeming it "primitive" and even calling Jamie a "Monkey-thing". But by the end of the show's run, she's accepted the company of her hosts, develops a taste for convenience-store slushies, and even ditches her military uniform in one episode to attend a rock concert with the boys.
Emma Frost in Wolverine and the X-Men. In the beginning, she is unflinchingly rude to most of the mansion's inhabitants; she even reads their minds before formal introductions can take place. She's pretty much what you would expect if you know anything about the comics. By the time the midpoint of the series rolls around, she's practically a different character. So much that even Wolverine, who never trusted her in the first place, is shocked by her betrayal. Even then, said betrayal doesn't last. Neither does Emma, sadly.
Marceline the Vampire Queen starts out as a hedonistic Jerk Ass who pretty much doesn't give a hoot one way or the other about anyone else, so long as no one's trying to stop her from doing her thing, but after Finn showed her a good time by battling to the "Holy cow I actually felt that," she decided she liked the little spud after all. Every time she appears in an episode, she softens up a little more, and now Finn considers her one of his closest friends, and even Jake, who is apparently massively vampire-phobic, warmed up to her.
The Ice King actively averts the trope (and not just because he's a literal Ice King); initially he was portrayed as a malicious, sociopathic princess-kidnapper. As we gained some more insight into who he is, we actually find out that he's the way he is because he's lonely, and even kind of a dorkish weenie deep down, but has no idea how to deal with either of those things. But since the crown renders him entirely incapable of acknowledging his own faults, he's pretty much locked out of actual character development for any kind of defrosting.
The Adventures of Super Mario Bros. 3 has a literal, non-romantic example. King Windbag of Ice Land was formerly a bully, pushing his servant around and threatening him with his wand. Hip and Hop turn him and Luigi into dogs and in their quest to become human again are caught by a dogcatcher. With Luigi's guidance, the king learns how to cooperate with the other trapped dogs and they escape. Coming back to Ice Land as a human, he apologizes to his servant and throws him a feast in his honor.
ThunderCats (2011) with standoffish, gruff Old Soldier Panthro. When he and his Thundercats meet the genial Ro-Bear Berbils, a race of Cute Machineteddy bears, Panthro immediately announces that he doesn't trust anything this adorable. He is deeply flustered when they heap praise and affection on him after he uses his Genius Bruiser talents to repair and save the life of Ro-Bear Bill. When the Berbils show thanks for his help by replacing the engine of his Thundertank, Panthro bursts into Manly Tears.
A non-romantic example in My Little Pony: Friendship Is Magic: Twilight Sparkle starts out insisting that she has no interest in friendship, as her entire life is consumed with her studies and her duties to the Princess. The plot of the two-part pilot is all about her discovery that only by making friends can she unleash the full power of her magic and save the world.
Lance in Sym-Bionic Titan is initially a lot more quiet, reserved and focused more on getting his job done (to the point of harming citizens who didn't do anything wrong). Gradually, he warms up to Ilana and Octus as family and develops his own recreational hobbies on earth.