NOTE: This spoiler was sent in by Robert W.
The movie opens with a small prologue explaining Hellboy's entry into government services via still screens.
It then opens on Christmas Eve 1955, when a somewhat aged Professor Broom (John Hurt) ushers an early teens Hellboy to bed. He won't go without a story, so Broom pulls out a storybook and tells the story of a war between Elves and humans. After numerous battles, the Elves employ the services of an invincible Golden Army, who crush human forces without much work at all. However, the Elf King is crushed by these losses, and calls for a truce between the two parties. The Golden Army is shut down and stored, although Prince Nuada, the Elf King's son, disagrees and vanishes, vowing to "come back when his people need him". Broom closes the storybook and Hellboy asks if it's true. He states that it's for him to decide and Hellboy goes to sleep, a big smile on his face.
Switch to modern day. The grown-up Prince Nuada (Luke Goss) is swinging around a weapon in a subway tunnel as a train passes by. He calls upon his "friend", hiding in the shadows, and tells him it's time to resurface. The scene then changes to the Manhattan streets, at a nearby auction house. The auctioneer is auctioning off a weird fat Tibetan female statue when Nuada sneaks in, killing a guard before he's noticed. From there, Nuada bursts into the room, carrying a crate with a Royal Seal on it. The auctioneer calls for security, but then two guards come crashing through the door at the hands of Nuada's right-hand man, Wink, with a fist attached to a chain. He reels it in and stomps into the room, placing another container with a seal down next to him. Nuada then throws a squid-like creature on the auctioneer's face, killing him, and condemning the rich people in the room. He then opens the crate, little creatures jump out, and the screen fades to black.
The scene then shifts to the Bureau for Paranormal Research and Defense, guarded by patrollers. Agent Tom Manning (Jeffrey Tambor) walks in, going up to Abe Sapien (Doug Jones) and showing him a "top secret" file. They go down to talk to Hellboy, walking past a few strange creatures and agents in the process. Suddenly, Hellboy's vault door bursts open, swinging past Tom and Abe and slamming into the wall. Abe explains that he and Liz Sherman (Selma Blair), his pyrokinetic girlfriend, are having trouble. Hellboy (Ron Perlman) and his girl set their issues aside to load up, and Tom makes Hellboy promise that he'll stay in the shadows, since he's been in photographs recently (he even autographed one).
They get to the desecrated auction house and look around, and Hellboy has a quick chat with Abe about Liz (which Liz overhears). Suddenly, the little creatures -- Tooth Fairies -- scamper about. One crawls in the open and attacks an agent, and HB crushes it with his hand. The rest attack, making small work of the human agents while HB, Abe and Liz fend them off. HB grabs the Tahitian statue ("Sorry lady!") and rolls it on numerous creatures. Abe goes to hide in a vault as Liz lets loose with a fiery explosion that kills most of the creatures. Hellboy stands by a window and willingly launches himself through it, landing in the city street where Manning is keeping reporters at bay. A couple of the Tooth Fairies manage to escape with him, but HB shoots them. Reporters start asking him questions while Manning shows his frustration. Abe and Liz walk out as well, surrounded by reporters.
Back at the Bureau, HB is watching on TV as the coverage of their exposure goes around. (There's even a Jimmy Kimmel clip.) Liz is somewhat frustrated, after Abe has discovered that she's pregnant. She goes through a few pregnancy tests and they come back positive. Manning is absolutely upset, and explains to HB how he screwed him over. HB doesn't see it as a big deal.
Meanwhile, Nuada, claiming a piece of a crown needed to control the Golden Army from the auctioneer's house, visits his father, hiding in a deep dwelling in New York City with the rest of the elf clan. He explains that the human race has let itself go and he needs to retaliate by reactivating the Golden Army. His father refuses, and orders his soldiers to kill Nuada. He fights his way out of the death circle, eventually slaughtering his father's guards and stabbing the king in the heart. He turns to stone, but not before Nuada steals his piece of the crown. He goes to get the final piece from his sister, Princess Nuala, but she runs off before he can retrieve it.
Back at the Bureau, Manning explains that a new specialist has been brought in to take charge of the team, since HB is so lousy at following orders. In steps Johann Kraus (voiced by Seth McFarlane), a gas-like creature in a big metallic suit. He studies one of the Tooth Fairies and through temporary body control, insists that the answers lie in a hidden Troll Village. He orders the team, including Manning, to follow him.
At a back alley, the team watches the scene using special goggles that show people for what they "truthfully" are. They see an old lady in the corner who's really a nasty looking troll, but let her be so they can follow her in. She's about to eat a cat, and since HB cares about cats, he interjects, telling the lady he can see her for what she truly is (despite Johann's objections). Liz and Manning wait in the truck while HB, Abe and Johann follow the old woman through the hidden entrance of the Troll Village. HB knocks her away (after threatening her with a canary) when she refuses to cooperate, and Johann releases himself in gaseous form to activate the gears, which open the gate to the Village.
The three look around the Village, with Johann trying to ask questions politely and HB using his usual brute force. Abe, however, locates Nuala, from the Royal Seal on her arm. He follows her into a nearby shop, where they discover who they are through their psychic abilities. Nuala explains Nuada's plan to resurrect the Golden Army. Wink suddenly shows up and proceeds to beat up Abe while Nuada escapes. Abe doesn't fight back, but he does evade the incoming attacks quite nicely. HB then shows up and he dukes it out with Wink, and they fight all over the village. Wink is eventually brought down for the count, but gets back up. He launches his fist at HB, but it lands in a grinder, which drags Wink right along into it, killing him. Johann states they can't take Nuala with them (government orders), but HB balks at his order and says she's coming along. Meanwhile, a freakish-looking spy informs Nuada (who's hiding beneath the village) that Wink is dead.
The group returns to the surface, with Johann and HB continuing to argue over Nuala. Nuada suddenly appears, and throws an elemental creature into a nearby sewer, before Abe can catch it. He then vanishes just as quickly, and a huge green-ish monster emerges from the ground, attempting to kill HB. He loads a huge gun called the "Big Baby" and proceeds to battle the creature. He stops to save a baby from a locked car, and carries the child as the creature smashes cars and everything else all around him. He climbs up a hotel sign, throwing the kid in the air to load the Big Baby and catching him. He then fires, hitting the creature a couple of times and stunning it so it attaches itself to a nearby building. Nuada appears again, questioning HB's choice to not kill it right away. He then poses the question as to whether he takes the human or inhuman side. Just then, HB finds himself forced to kill the creature, which collapses to the ground and grows grass and other plant life in its wake. HB climbs down after Nuada vanishes (again), facing ridicule from the crowd for endangering the baby's life. The police point their guns at him, but Liz holds them off by setting herself on fire. The crew leaves.
Back at the Bureau, Nuala is reading from a classic literature book and catches Abe's eye. They have a clear fascination for each other, and here she explains that she's connected to Nuada, since they are identical twins and feel each other's pain. She shows a map inside a cylinder, but it's blank, with no real marks on it. (This is to reveal the location of the Golden Army.) She goes to bed before Abe is able to tell her how he feels about her.
Meanwhile, with Liz sleeping, HB begins sulking about her feelings for him. He takes a shower while drinking a beer. When he gets out, Johann confronts him about how his temper gets the better of him. Proving his point, HB smashes in his dome after being threatened, that Johann can "take him". His mist escapes into the locker, where he swings open several locker doors, beating the living crap out of HB. He then returns to a gaseous, ghostly form and leaves, but not before telling HB he really needs to control his temper.
Outside of the Bureau, Nuada arrives, after he's made quick work of the patrolling guards.
HB pops in on Abe while he's playing a Barry Manilow song. He finds out that Abe has a thing for Nuala, and offers him a beer. The two of them sing along to the song for a moment (funny scene) before drunkily heading back to where Liz is sleeping. The two are talking and Abe almost gives away the fact that Liz is pregnant, but she stops him before he gets there.
Nuada catches up with Nuala in the main library, where she's hidden the final piece of the crown and put the cylinder and map in a fire. Nuada grabs the cylinder and rolls it on the table, revealing the real map as it burns into it. He shows the location of the Golden Army, then demands the final crown piece. Nuala activates an alarm. HB, Abe and Liz, along with several agents, reach the library. Nuada challenges HB, who drunkily accepts and stumbles into a fight. Nuada ends up stabbing him near the heart, leaving the blade in his chest. He tells Abe that if he wants HB to live, and if he wants to see Nuala again, he'll bring the final piece of the crown to him, at the location of the Golden Army.
After Nuala and Nuada leave, Abe attempts to retrieve the sword piece from HB's body, but it sinks deeper with each attempt. Liz demands that they meet up with the prince to save HB, but Manning and Johann vehemently disagree (government orders). She talks with Abe, who's found the final crown piece in the book Nuala was reading, and says they need to go anyway. They prepare a plane, but Johann shows up. At first, he's questioning why they need the plane, but he sees Liz's care for HB and agrees to come along, denying the orders.
The plane arrives off the coast of an island in Ireland, and the four make their way up a mountainside, where they run into a local goodsman dragging a wagon. He shows them a hidden entrance into a lair where someone can help HB. They barely reach it when HB collapses, and the figure, the Angel of Death, talks to Liz. He says that he can save HB, but he's a harbinger of doom that could end the human race. He even shows a figure in the ground to prove this. He then asks Liz to choose between humans and HB, and she chooses HB. He says she will suffer for this, and she states she'll deal with it. The Angel removes the shard from HB's chest, and Liz tells HB to wake up because he's about to be a father. HB awakens and the two embrace.
The goodsman leads the four of them down to a hall containing the dormant Golden Army. They climb the stairs and meet with Nuada, who's holding Nuala and demands the final crown piece. To protect the woman he desires, Abe throws him the piece, much to HB's discontent. Nuada forms the crown and the Golden Army awakens, charging up the stairs. He orders the Army to kill them. Abe is upset that he lied, but HB explains that, if they live, they'll talk about that later. HB proceeds to blast several Golden Army members with his gun, while Johann escapes his suit and takes possession of one of the Army, crushing others with his fists. HB grabs one of their arms and swings it around like mad, taking them down. However, several other members are approaching, and the damaged Army members easily rebuild themselves. It's a lost cause.
HB sees one way out of this -- he challenges Nuada for control of the Golden Army. He has the right to do, claims Nuala. The two fight it out across numerous gears and such, before HB finally gets the jump on Nuada and defeats him. He doesn't kill him, though, as Abe states that he'll kill Nuala as well. HB takes his crown and walks away, and Nuada pulls out a dagger to stab him from behind. To stop him, Nuala stabs herself. Abe rushes to talk to her while Nuada explains that HB may have chosen the wrong side. Abe and Nuala have a moment of connection. The two of them die, and Liz melts the crown, shutting down the Golden Army.
The crew walks out of the cave entrance to find Manning and his men waiting, wondering why they took a plane without clearance. Without hesitation, HB quits, with Liz and Abe following. Johann quits as well, telling Manning to pretty much kiss his butt in a funny German phrase. The crew then walks down the mountainside, and HB talks to Liz about how they can get a nice house for them and their kid. Liz corrects him by stating that they're going to be having twins. HB looks at her dumbfoundedly as Barry Manilow plays in the background and the movie ends.
After following a centuries-old order that keeps peace between elves and humans, Prince Nuada (Luke Goss) chooses to revive a Golden Army, after humans have grown slovenly. He murders his father to get a crown piece and pursues his sister.
Eventually, he gets the final piece, activating the Golden Army. However, Hellboy (Ron Perlman) challenges him to a fight and beats him, and he and his sister, Nuala, die in the process. The Golden Army shuts down.
Hellboy and the others quit the agency to live a new life, as he and Liz (Selma Blair) are expecting twins. However, an Angel of Death informed her earlier that HB is really a harbinger of doom, and may have sealed the fate of the human race.