Hellboy might not have the name-recognition factor of the Spider- or Batmen, but Guillermo del Toro brings the audience swiftly up to speed on artist-writer Mike Mignola's comic book anti-hero.
First, he treats us to an atmospheric World War II prologue. Then we meet the present-day Hellboy: a hulking action guy with red skin, sawn-off horns, a stone right hand and teenage jock attitude, coping with ickily-tentacled threats to the fabric of reality while nurturing a crush on a fellow agent, troubled pyrokinetic ("I hate the term 'firestarter'") Liz Sherman (Blair).
There are many characters and situations to introduce - also on hand is sensitive fish-man Abe Sapien (voiced by David Hyde Pierce) - so del Toro brings in a new BPRD agent (Evans), developing a romantic triangle by having him warm to Liz. This thread is easily the flimsiest, but so much else is going on that it doesn't get in the way.
Del Toro turned down opportunities to make this with a bigger budget in return for putting a star in Hellboy's giant boots, but he was right to hold out for Ron Perlman, who's more used to jobbing as a character actor. Thanks to his gruff, blue-collar charisma, a character who could easily have been just a big, scarlet special effect works like gangbusters.
Meanwhile, Blair and Hurt (as the hero's adoptive pop) provide calming influences, but the best supporting turn comes from the always-welcome Jeffrey "Hey now!" Tambor, as the smarmy bureaucrat boss.
Del Toro's already been down the comic-adaptation route in Blade II (which now looks like a practice run), but Mignola's series is far more congenial material for cinematic treatment, with its blocky stone-and-iron architecture translating wonderfully to the screen. It's just a shame the promised reign of giant evil squid gods is too nebulous a threat to play as well as an old-fashioned fist-fest.
As usual, a human-shaped foe (here, Kroenen - a near-immortal Nazi assassin in stylised gas-mask, with a wind-up key in his heart and dust in his veins) is more interestingly hateful than the pile of CGI tentacles brought on for one last bout after the show is really over.