So Brienne of Tarth (PotS) is one of those cards that a newer player (like me) may initially scratch their head at. Ok, I'm sure that's a good ability in some cases. Then I built a Stark Siege deck and ran up against her. If the opponent has her out and she and defends in a military challenge I cannot a) claim power using the Siege of Winterfell agenda's response, or b) play murder events. Or use the Blackfish's response. Etc. etc. etc. Plus, she's Stark, so she is immune to Bear Island. That really shuts down this kind of deck, and she cannot even be taken out with most of Stark's tools for dealing with troublesome characters.

Anyway, here is my deck, and I'm wondering what I could change to make sure I can deal with Brienne:

Deck Built with CardGameDB.com GoT Deckbuilder

Stark Siege

House (1)
House Stark (Core) x1

Agenda (1)
The Siege of Winterfell (LoW) x1

Character (32)
Bolton Refugee (RoW) x3
Brienne of Tarth (PotS) x1
Carrion Bird (ASoS) x2
Catelyn Stark (LoW) x1
Hodor (Core) x1
Knight of Harrenhal (TBC) x2
Knight of the Tumblestone (Core) x2
Lucas Blackwood (GotC) x1
Maester Luwin (FtC) x1
Maester Aemon (Core) x1
Meera Reed (TftH) x3
Northern Cavalry Flank (SA) x3
Randyl Tarly (KotS) x1
Robb Stark (LoW) x2
Ser Jorah Mormont (PotS) x1
Ser Kyle Condon (APS) x1
Ser Rodrik Cassel (Core) x1
The Blackfish (LoW) x2
The Hound (PotS) x1
Host of the Bear (LoW) x2

Location (16)
Street of Steel (LoW) x1
Street of Sisters (Core) x1
Street of Silk (LotR) x1
Narrow Sea (LoW) x3
Lord Eddard's Chambers (Core) x1
Great Keep (LoW) x3
Harrenhal (ODG) x1
Frozen Outpost (LoW) x2
Bay of Ice (KotS) x3

Event (8)
Die by the Sword (LoW) x3
No Quarter (TBC) x3
Endless Endurance (LoW) x2

Attachment (4)
Bastard (LotR) x2
Frozen Solid (LoW) x2

Plot (7)
Retaliation! (ASoSilence) x1
Storm of Swords (LoW) x1
The Power of Arms (Core) x1
Wildfire Assault (Core) x1
At the Gates (GotC) x1
Fear of Winter (BtW) x1
Forgotten Plans (KotStorm) x1

My ideas so far:

1. Switch Wildfire out for Valar
2. Switch Endless Endurance for Nightmares
3. Add more deadly / stealth?

Swapping Endless Endurance for Nightmares will probably cover you for most of it. You could swap out a Bastard for a Milk of the Poppy if you are really worried. Meera Reed should be covering Brienne most of the time. If you are having trouble getting her back into Shadows, swap Maester Aemon for Ghost from The Wildling Horde. Not only does he add Stealth, but his "return to hand" at will effect allow you to return Meera to Shadows pretty much at will, too.

If you are winning Dominance a lot, consider the "Turncloak" attachment.

Syrio Forel would give you another cheap stealth mil icon to use against her (and in general). Damon Dance-For-Me is another strong mil icon who will in all likelihood have stealth.

If you use TWH Ghost, you could consider Icy Catapult. Expensive, but gives you the targeted removal; could also be combo'd with a refugee or some chump who is then killed with Wildfire Assault.

I recently got a friend into the game and they went and net-decked some Baratheon wildling deck that uses Brienne (much to my chagrin, as I would prefer if they experimented with builds rather than taking someone else's winning strategy…) and played it against a Greyjoy Raider deck I was in the process of trial testing… It completely shut down my deck, which relied on Maester Wendamyr and KotHH to keep all of my expensive characters safe until I could build up a wall of raiders and crush him. How would you guys recommend dealing with her on the defensive, when she is shutting down Greyjoy's greatest asset (it's saves)? I added in the 2 Milk of the Poppy (core)'s that I have, but I don't know what else I should put in, as relying on two cards out of 60 is inefficient.

*Not trying to hijack the thread, I just figured I'd ask in here, as you were already on the topic of Brienne (I'll make my own post if it comes off that way)

Fishing Net - Bara doesnt have good attachment control. Pulled Under can be useful and is actually affordable in a KotHH deck; remember that your opponent cannot save against it.

Great suggestions! I don't have Pulled Under, but I will definitely add 2 or 3 Fishing Nets.