Quinn works as a stripper at The Lusty Leopard, a strip club Barney frequents. She gained a keen perspective on Barney's character over his multiple visits, though Barney never memorised her.
Barney tries seducing Quinn at a nightclub, only for her to shoot him down. Barney later confided to his friend Ted about how frustrated he was, which Ted interpreted as genuine attraction. Barney later reveals that they somehow formed a connection and Quinn slept with him. Elsewhere, Quinn complains about Barney in a similar manner to one of her co-strippers. The stripper then tells Quinn that she must like him
Barney soon finds out that Quinn is a stripper. He tries asking her out, but Quinn exploits Barney's attempts to get close to her by forcing him to pay for lap dances. Barney is initially led on by this, but after seeing Quinn use the exact same technique on a creepy middle-aged man, Barney realises how little Quinn thinks of him. The morning after, Barney runs into Quinn at a coffee shop and calls her out for manipulating him. Quinn then reveals how much of their conversations she remembered and Barney realises that maybe they could work.
Barney and Quinn then start dating. Barney's friends think Quinn is bossy and try to get him out of the relationship, culminating in a big fight between Barney and Quinn. It was revealed immediately afterwards that Barney and Quinn were just playing the gang for their own amusement, showing that Quinn has the same mischievous streak that Barney has.
Quinn moves into Barney's apartment, making her the first woman Barney has ever lived with. Barney also finds out that Quinn would consider a career change if she ever got married. Barney is secretly put off by thre idea that Quinn is a stripper and tries spending his nights doing increasingly outlandish things in an effort to distract himself. Quinn finds out about this after Barney tried getting her a job and tells him to sort out his insecurities, saying she wasn't ashamed of herself. Barney then books them a holiday in Hawaii to help get the relationship back on track. When the airport security finds some suspicious luggage on Barney, they hold them up. Barney reveals that the box he was carrying was part of an elaborate magic trick that he was planning to use to propose to Quinn. Quinn happily says yes.
Over the Summer, Barney and Quinn plan their wedding. When it comes to the pre-nuptial agreement, Barney tries to get Quinn to agree to some truly demeaning things such as making sure she stays thin and allowing him to sleep with her stripper friends. Quinn replies by making Barney agree to avoid being near attractive women for as long as he lives. Both try getting the gang involved, which leads to a massive fight that spills into all of the gang's relationships. Barney and Quinn then realise that if they're fighting over a marriage contract they probably aren't close enough to get married. Feeling the relationship has come as far as its going to go, they break up.
Quinn would later appear at Barney's bachelor party, resuming her previous occupation as a stripper.
Barney never told Quinn that Robin was his ex-girlfriend. When Quinn found out, she felt threatened by Robin's prescence and suspects that there might be some lingering feelings. Barney reminds Quinn that Robin is dating someone else and they were much better off as friends.
After Barney and Robin get engaged, Robin sees Barney with Quinn after his bachelor party, attacks her on sight and threatens to break off her engagement. This was later revealed to be a prank concocted by both women to keep Barney loyal to Robin.