During the War of the Five Kings Tarth declared for King Renly Baratheon and Brienne joined his army. She won a melee at Bitterbridge and secured a place in his Rainbow Guard. She has been in love with him since the first time the met, when he as the Lord of Storm's End was making the rounds of his bannermens estates and stayed at Evenfall hall. When Renly was killed under unusual circumstances, she was accused of the deed, but fled with the help of Catelyn Stark and though she wouldn't agree to join the Stark cause, she swore fealty to Lady Catelyn.
She later escorted Jaime Lannister back to King's Landing at Catelyn's order, but by the time she arrived there was no way to complete her mission to bring Lady Catelyn's daughters back to her. Lady Catelyn was dead killed at the Red Wedding, Arya had never been in Lannister custody, Sansa was married to Tyrion Lannister, and had disappeared. In King's Landing, Ser Loras Tyrell insists that she be imprisoned, which Jaime agrees to for her own protection. Loras talks to her and comes to realize that she did not kill Renly.
Jaime is grateful that Brienne brought him out of danger and he has come to admire her. He gives her his new Valyrian steel sword and charges her to scour the Riverlands looking for Sansa and Arya. He says that she will be his honor and after this Brienne starts to think and dream of Ser Jaime all the time.
As she travels, she realizes that she is being followed. It is Podrick Payne, Tyrion's squire who is trying to find his master who deserted him. Brienne takes him on as her own squire. And begins his serious training in arms.
Though highly trained in arms it is not until the book Feast of Crows that Brienne kills her first man. She is relieved to do it without flinching, which she has always worried about.