Dye or Die

Nice, distinctive hair you have there, Ms Heroine or Mr. Hero! But sadly, it's going to be a problem for you. Perhaps you find yourself in the midst of a Stern Chase, dodging trouble from the Space Mafia or close to getting your secret agent cover blown. You have a choice: Dye or Die.

So, you have to dye your hair as a disguise. Bye-bye, blonde highlights.

Men will also have to shave their mustache or beard, if they have one. Maybe grow one if they don't.

Compare Important Haircut, Expository Hairstyle Change, Wig, Dress, Accent (without the wig, the dress, or the accent), Kaleidoscope Hair (if it happens many times), and Clark Kenting.

Examples of Dye or Die include:

Anime and Manga

Victorique from Gosick to avoid pursuers.
Jinto makes Lafiel dye black the blue hair that marks her as an Abh in order to avoid notice by the invading United Mankind in Crest of the Stars.
In the 2003 anime version of Fullmetal Alchemist, Ed dyes his (long blond) hair brown, and wears stilts and a hat in order to disguise himself.
In Mahou Sensei Negima, Setsuna, after being exiled from the crow demon tribe for being a white-feathered half-demon, and there being demons and humans more than willing to hunt down and kill half-demons, dyed her also-white hair jet black to live in normal society. Her wings are still white.
In Sword of the Stranger, Nanashi aka Nameless in the literal sense, dyes his red hair black to avoid trouble. Seems like the residents in feudal times hated foreigners.
J, the cult's second in command of Bloody Monday, in the most recent chapter, is sporting a different hair color.
Yoko in The Twelve Kingdoms spends a pretty good part of the first arc with her distinctive bright red hair (which had changed color when she arrived in the Kingdoms) dyed a much less obvious shade of brown to help throw off pursuit.
Eureka has to do this in Eureka Seven AO so she and her son can avoid discrimination from the islanders and attention from foreign governments.

Comic Books

Done in Watchmen by The Silk Spectre II and Nite Owl II, when they assume new identities at the end, having allowed everyone to assume they died in the Big Bad's attack on New York. They both dye their hair blond. Also, Nite Owl II grows a mustache and Silk Spectre II cuts her hair.
In Iron Man, Tony Stark shaves off his beard and dyes his hair blond while on the run. It works, as no one recognizes him, but he feels he looks like "an idiot".
Played for laughs in Why I Hate Saturn: brunettes Anne and Laura are on the run from Laura's ex-boyfriend and they dye their hair blonde so they won't be recognized. When he finds them anyway, they run again, and Laura decides to return her hair to its original color - only she messes up and it comes out green!
In Omaha the Cat Dancer, the title character bleaches her hair blond before fleeing Mipple City after she and Chuck had a severe falling out. Eventually, she decides to return and goes to her favorite hair stylist to put her hair back to normal. That proves a very unpleasant experience even as the stylist makes her opinion clear that Omaha shouldn't have abused her hair like she did, in other words, "Next time you get an idea about your hair? Call for a second opinion, Okay?"

Film

Done by Marie in The Bourne Identity and later Nicky in The Bourne Ultimatum.
Harrison Ford in The Fugitive.
Done by Evelyn Salt in the movie Salt.
Agent 99 in the 2008 Get Smart movie - but her dye job is incidental next to the extensive plastic surgery she undergoes to keep her job as a secret agent.
In Dutch WW 2 drama Zwartboek AKA Black Book in order to spy on the Nazis, the Jewish main character Racheal had to dye her brown hair blond, and not just the hair on her head( since this is a Paul Verhoeven film guess which one was shown).
In Species, after faking her death in a car crash with one of her own severed thumbs Sil cuts her long blonde hair short and dyes it black to hide from the scientists who are hunting her.
Inverted in The Long Kiss Goodnight where the lead's usual hair is dyed blonde during her time as an assassin. When she loses her memory, she lets her natural auburn hair grow out. The CIA is still able to recognize her on video, despite a drastically different style of clothing as well.
Attempted by a cavewoman mother in When Dinosaurs Ruled the Earth as that tribe had a tradition of sacrificing blondes to the sun. Of course, she attempted said dye job with tar.
The Day of the Jackal.

Literature

In The Outsiders, Johnny cuts and dyes Ponyboy's hair blonde when they go on the run after Bob's death.
Nynaeve, Elaine and Birgitte in The Wheel of Time.
In The Thief Lord, Hornet dyed Bo's angel-like blond hair black with ink to fool the detective that was searching for Bo and his brother.
Sansa in A Song of Ice and Fire.
- This one was particularly subtle. She has a distinctive shade (Auburn) of brown hair. So she dyes her hair a more normal mousy brown.
Abby in The Firm.
Zakath grows a beard as part of not being recognized in The Malloreon. Belgarath dyes Garion's sandy blond hair dark brown for the trek across Morindimland. Polgara has tried dying her hair in the past to hide, but her Skunk Stripe always comes back and makes it impossible.
- Reversed nicely at one point in the prequel novels. Dye won't adhere to Polgara's white lock, and she's trying to be undercover. So Belgarath (in his wandering storyteller disguise) starts telling ladies across the western kingdoms that the latest fashion in hairdressing is dark hair with a dyed-white streak in it.
In The Awakening by Kelley Armstrong, Chloe's blonde-with-red-streaks hair is recognized by a by-stander, and so she is forced to dye it black. Since she's a sheltered fifteen-year-old and the new color looks atrocious, this is very upsetting to her.
In the Holocaust-set novel Number the Stars, Peter has distinctive red hair and must keep a hat on it to keep the Nazis from finding him.
Sharrow in Iain M. Banks' Against a Dark Background goes so far as to shave her head in an attempt to throw off her pursuers.
Somewhat like the Polgara example above, it's mentioned a time or two in the Heralds of Valdemar stories that Companions can't be dyed—or rather, the dye job never lasts long enough to do much good.
In I, Jedi Corran Horn dyes his hair and grows a goatee in order to attend Luke Skywalker's Jedi Academy without openly being a hero of the Rebellion and drawing too much attention. The dye, being special dye with a metabolizing agent, is initially misused, making him green-haired from head to toe, and he has to call his old Space Cop partner for help.
- Isard's Revenge has Wedge Antilles donning cyborg guise and growing out a beard in order to disguise his famous face while on The Infiltration.
  - The cyborg disguise is a Call Back to Wedge's Gamble where he impersonates the same person when infiltrating Coruscant.
used by Ani (Isi) in Goose Girl. Since only her countrymen( read: the traitors that want to KILL her) have blond hair, she tries to dye her butt-length yellow locks. Subverted in that she can't find enough brown dye, as it's uncommon in Bayern, and settles for wearing a scarf and only dying her eyebrows.
Both Aiden and Meg Falconer in On The Run. Meg bleaches and cuts her dark hair, while Aiden dyes his blond hair brown.
Poked fun at in an early Gor book when one of Cabot's friends, pretending not to recognize him, comments that Tarl Cabot's hair is a magnificent shade of red, "whereas yours is a rather common and, if I may say so, a rather uninspired black."

Live Action TV

Used in Heroes, season one, 'Five Years Gone.' Claire's iconic blond locks have been dyed brown.
Dr Richard Kimble dyes his grey hair black in The Fugitive.
Done in the TV adaptation of the Covert-One novel The Hades Factor, with the character in question (going from redhead to blonde) referred to as the "Killer Blonde version".
Doctor Who: In "The End of Time", the Master dyes his hair to avoid being recognised as the former Prime Minister. It only gets weirder from there.
- Actually, his hair is white because his resurrection was screwed up.
In the Highlander episode 'Methuselah's Gift', Amanda does this when she's being chased by mortals who want her crystal. She bleaches her dark hair white.

Video Games

Heather/ Cheryl/Alessa, in Silent Hill 3, has her hair dyed blond as part of her disguise to avoid the titular town's cult. Her father probably does this from the time she's young, and she apparently continues doing it when she gets older.
- She is a teenager, however, so it might have been a style choice.

Web Comics

Kathryn Flinders in Schlock Mercenary had a brief disagreement with the Toughs and was hiding from them, then stuck with the new look, without any particular reason. Before, after.