Lúthien Tinúviel and Beren. He is a mighty physical warrior. She is a elf sorcerer capable to bring down a fortress and put the God of Evil of her world to sleep. Together they complemented each other's skills, humiliated Dark Lords, and their deeds were theme of songs seventy centuries after their deaths.
Ellie and Will from Courtney Allison Moulton's Angelfire series who take on demonic armies together.
Aldrea the Andalite meets Dak Hamee, the Hork Bajir seer, during the battle to keep the Hork Bajir home world free from the Yeerks. Almost a whole book and several lifestyle-related struggles later, they become a mated pair, give birth to a son, and decades later their descendants form the first members of the free Hork Bajir on Earth.
Kate Daniels and Curran from the Kate Daniels series, often fight together and never lose.
In Black Dagger Brotherhood novels, this trope is inverted with Xhex and John, as fighting together causes major problems in their relationship. Though he knows that she's a capable warrior, bonded males are genetically hardwired to protect their mates at any cost, so his instincts keep firing up on the battlefield and putting them both in danger. This pisses her off as she thinks he doesn't respect her skills; they separate for a good long while because of it.
Ruggiero and Bradamante from Orlando Furioso. When they're reunited halfway through the work, the first thing Bradamante does is go off to save a dude, and Ruggiero is thrilled to have a woman understand what he does.
Slippery Jim diGriz (The Stainless Steel Rat) and Angelina, his wife and fellow criminal genius. He's a criminal mastermind who dislikes killing. She's a formerly-psychotic criminal mastermind who bemoans the fact that she can't casually kill people now she's had a conscience implanted. They Fight Crime!with crime.
The mixed-gender Valhallan 597th features several couples. These include Cain's own liaison with Lady Inquisitor Amberley Vail, as well as a male trooper named Vorhees and a female trooper named Drere in Caves of Ice, and a strongly implied lesbian relationship between Sergeant Grifen and trooper Mari Magot in the same book.
Cain invokes this trope; relationships in the guard normally aren't allowed but Cain allows it because it improves morale and makes them fight harder.
Colonel Kasteen and Major Broklaw, the commander and Number Two of the 597th respectively. Nothing romantic is ever confirmed in-story, but Broklaw refers to Kasteen by her given name, implying they're on First-Name Basis — which is highly unusual for a relationship that's merely commander-subordinate.
Amelia Peabody and her husband Radcliffe Emerson, Egyptologists and incidental detectives in the Amelia Peabody mysteries by Elizabeth Peters. The stories are set stretching from the Victorian era into the Roaring Twenties. Peabody and Emerson are grandparents, now, but that only slows them down a little. They have produced a second generation Battle Couple, their son Walter "Ramses" Emerson and his wife Nefret. The third generation is alarmingly precocious and will almost certainly turn out to be Meddling Kids.
Picker and Blend are a lesbian battle couple. They've been going steady ever since joining the Malazan army. Picker is proficient with the sword and crossbow, while Blend prefers long-knives and stealth, and Blend acts like something of an aide for (first Corporal then Lieutnant) Picker as they need little words to communicate.
Dawn and Julius in The Radiant Dawn. Played oddly because Julius is fully willing to not contest Dawn charging into battle against clearly defined enemies and assumes she can handle herself, but worries greatly about her being stabbed in the back by someone she doesn't think is an enemy.
Aral Vorkosigan and Cordelia Naismith meet in this fashion. They take out the mutineers on Vorkosigan's crew (twice).
Admiral Naismith/Miles Vorkosigan and Elli Quinn are a straighter example of this. She dual hats as his intelligence chief and executive officer when he leads the Dendarii Free Mercenary Fleet. The relationship ends when Miles is forced to retire to civilian life.
In general the Star Wars EU is full of these with the majority of the main couples being battle couples.
Wedge and Iella, Corran and Mirax, Kell and Tyria, Face and Dia, Gavin and Asyr Myn and Lara... it should go without saying that the X-Wing series of the Star WarsEU, being about fighter pilots, has a lot of these.
One interesting example due to their main allegiance being to the Jedi Order is Obi-Wan and Siri in that they both realize that they would rather be Jedi than in love, making them a Battle Not-Exactly-Couple.
Every time Heralds and/or Hawkbrothers get together in the Heralds of Valdemar series: Talia and Dirk, Elspeth and Darkwind, Kerowyn and Eldan .... A specific exception is Alberich and Myste; Alberich is the series' resident Empowered Badass Normal while the Author Avatar Myste, Herald or no, is a bookish librarian.
In the third book of the Mistborn series, Elend and Vin go beyond the Bodyguard Crush relationship of the second book and straight into this following Elend turning into a full-on Mistborn.
In the third book of The Bartimaeus Trilogy, Nathaniel and Kitty become this, almost kissing just before his heroic sacrifice.
Nightside: Suzie Shooter and John Taylor have been known to kick some serious ass, although their couple status is still a work in progress.
The Wheel of Time: The main plot of the series involves everyone preparing for The Last Battle, so every named couple falling in this trope. A few examples are Rand and Min/Aviendha/Elayne, Lan and Nynaeve, Egwene and Gawyn, Perrin and Faile, Siuan and Gareth, a few Aes Sedai and their Warders, a few Asha'man and their Warder-like Aes Sedai, and countless Aiel couples.
Harry and Ginny fit on the occasion they fight together against their enemies. At the end of book six Harry tried to defy this trope by saying It's Not You, It's My Enemies but she wasn't having any of that.
Since everyone joins in on the last battle in Deathly Hallows, Lupin and Tonks, Mrs. Weasley and Mr. Weasley, and Fleur and Bill also count.
Likely the Potters and the Longbottoms were Battle Couples during the first incarnation of the Order Of The Phoenix.
As shown on the covers of The Alien Series, Kitty and Martini believe that the couple who kicks ass together stay together.
The Amazon Legion invokes this intentionally with the Tercio Gorgidas, a tercio (roughly equivalent of a regiment) comprised of homosexual male pairs who are married in a special ceremony, with an explicit nod given to the Sacred Band of Thebes (see the Real Life section).
Bellisarius and Antoninia in Belisarius Series (and in Real Life, by the way) although they are usually in different theaters. Also Rao and Shakuntala. The Theodoran Cohort has a number of Battle Couples.
Richard and Kahlan are this and become more so after Richard taught her his methods of fighting. Zedd, Cara, and Nicci all take turns being the third wheel.
The Mord-Sith are this with the Lord Rahl. All of them. It's like a harem of dominatrix, Anti-Magic, Break the Cutie, magical-taser wielding Aryan bodyguards in various colors of leather!
Tales of Kolmar has a bunch. Jamie was Maran's bodyguard, though she became a good fighter herself. Much later Jamie and Maran's friend Rella become this while trying to protect Lanen and Varien. Lanen lacks the necessary speed and will to be a career fighter but has to try her best anyway; Varien is new to being human and doesn't know what he's doing with a sword, but he's unnaturally strong and very protective.
Alec and Magnus are respectively a Shadowhunter (i.e., demon hunter) and a warlock who become a couple over the course of the trilogy while fighting evil. They fight together as partners in the final battle of City of Glass, when a new rune allows pairs Shadowhunters and Downworlders (such as warlocks) to share their powers with one another.
Maryse and Robert Lightwood are a married couple of active Shadowhunters, although their partnership receives little "screen time," since they are not main characters.
Will and Georgia from The Dresden Files are a married couple of werewolves who fight as a well-oiled tag team machine.
Harry and Susan fit this trope, if only briefly.
Nathan and Elena, in The Memory Wars, have been lovers through most of their past lives, and can draw on centuries of shared combat experience to fight together with perfect precision.
Crown Prince Alaric of Caederan and his Love Interest (and future bride) Laeshana have a wonderful teamwork moment while fighting through roughly 500 fire-spiders.
Deuce and Fade from Razorland Trilogy start out as reluctant partners in the first book, but by the third they are battling Freaks side-by-side.
The Honorverse has Victor Cachat and Thandi Palane. He's a superspy, master of the Indy Ploy and ice-cold killer, she's a Super SoldierSpace Marine who is more lethal bare-handed than most people would be with machineguns. It was more or less love at first sight.
Ukiah Oregon: Ukiah and Indigo, Max and Sam, Atticus and Ru, Rennie and Helena. Ukiah's moms are the only couple in the series who aren't.
Auria and David from Those Who Cry Green Tears become this after Auria saves David from the Ombras (human eating monsters).
In the Ahriman Trilogy this is part of the purpose of the mage/warden relationship. While they aren't explicitly intended to be romantic arrangements, it's universally acknowledged that they often end that way. Simon Bell's parents were mage/warden before they married and had kids.
Averted and played straight in the Tairen Soul series. The magically enhanced empathy of Fey women means that they can't fight in close combat, as they feel the pain of everyone they kill. However, Ellysetta is immune to this effect because of the predatory tairen soul bonded to hers and fights alongside Rain in later books.
Sathel and Retina are a married couple and mercenary partners.
A newspaper writer inquired into the "working relationship" of mercenaries Tiza and Nolien but Tiza insisted that this wasn't the case. It's a hard line to swallow considering how closely they work together and how protective they are.
Darrow and Mustang from the Red Rising trilogy are definitely this trope. While most of the combat in the series involves large-scale military campaigns and space combat, whenever they're not carrying out their own parts of a multi-pronged gambit, they're right there in the thick of things with each other.
In Warrior Cats, most couples tend to be this since most characters are active fighters. Firestar and Sandstorm are one particularly notable example since an entire book is devoted to them journeying together outside Clan territory.
In A Song of Ice and Fire, we have a mild example in Aegon "the Conqueror" Targaryen and Visenya Targaryen. Aegon, being a typical Targaryen, married his two sisters and declared conquest on the continent of Westeros. They say that Aegon married Visenya out of duty (she was the eldest of the sisters) and Rhaenys out of love. Visenya was known as a great warrior and dragonrider, wielding a valyrian steel sword named Dark Sister. While Aegon may not have had any strong feelings for Visenya, she was still his wife and they conquered a continent together. Rhaenys was also a dragonrider but had not martial prowess under her belt beyond that.
Romeo and Dagger in Wander are a somewhat downplayed example. They're both more than competent fighters, and by the end of the novel are the only adult survivors of Camp Greenbow, but they only actually fight when they have no other choice, and their most badass moment together, fighting off a group of smilers while holed up in an abandoned farmhouse, occurs off-screen.
Night Huntress: Cat and Bones are this, as well as Leila and Vlad. Mencheres and Kira also qualify to some extent.
Red Rising:: Darrow and Mustang are this in everything from combat to politics.