Up-to-date as of April 2014.

Taking cues from this (outdated) list, I am color-coding these in terms of core stories which need to be read in order, related stories which can be read in the suggested order or at any time, and side stories, which are sort of stand-alone and don't impact the main plot. I do recommend reading everything you can get your hands on, though!

If you have access to the trade paperbacks, I am going to list the volumes each story appears in as a superscript. For example, Seed of Destruction is in the first Hellboy TPB and The Black Goddess is in the 11th BPRD TPB, so they'll look like this:

Seed of Destruction ^HB1

The Black Goddess ^BPRD11

HB: Hellboy
BPRD: BPRD
AS: Abe Sapien
LJ: Lobster Johnson
WF: Witchfinder
HoE: BPRD: Hell on Earth
HBiH: Hellboy in Hell
SH: Sledgehammer 44
HBBPRD: Hellboy and the BPRD
FU: Frankenstein Underground

If you don't have access to the TPBs, just ignore those notes!

--

Please note: Hellboy/BPRD is not published chronologically, meaning it jumps around in time a lot. This list generally follows publishing order, but some stories have placed ahead or behind according to what I think flows best. If you would like to see the chronological order of the stories, see this list here.

A LIST.
Seed of Destruction ^HB1
Untitled story from 1993 San Diego Comic Con (Anubis) ^HB1
Untitled story from Comic's Buyers Guide (von Klempt) ^HB1
The Corpse ^HB3
The Iron Shoes ^HB3
The Chained Coffin ^HB3
The Wolves of St. August ^HB3
A Christmas Underground ^HB3
The Lost Army by Christopher Golden ^(novel)
Heads ^HB4
The Baba Yaga ^HB3
Wake the Devil ^HB2
Almost Colossus ^HB3
Abe Sapien vs. Science ^BPRD1
The Penanggalan ^HB7
The Crooked Man ^HB10
The Nuckelavee by Christopher Golden & Mike Mignola ^{(short story; Odd Jobs)}
Goodbye, Mr. Tod ^HB4
The Varcolac ^HB4
The Right Hand of Doom ^HB4
Box Full of Evil ^HB4
Pancakes ^HB4
The Nature of the Beast ^HB4
King Vold ^HB4
The Bones of Giants by Christopher Golden ^(novel)
Being Human ^{BPRD: Being Human}
Conqueror Worm ^HB5
The Killer in my Skull ^BPRD1
Hollow Earth ^BPRD1
Drums of the Dead ^BPRD1
The Third Wish ^HB6
The Soul of Venice ^BPRD2
Night Train ^BPRD2
Dark Waters ^BPRD2
There's Something Under My Bed ^BPRD2
Another Day at the Office ^BPRD2
Dr. Carp's Experiment ^HB7
The Ghoul ^HB7
The Hydra and the Lion ^HB7
The Vampire of Prague ^HB7
The Troll-Witch ^HB7
Born Again ^BPRD4
Plague of Frogs ^BPRD3
The Dead ^BPRD4
The Island ^HB6
Makoma ^HB7
Revival ^BPRD12
War on Frogs 1-3 ^BPRD12
The Black Flame ^BPRD5
War on Frogs 4 ^BPRD12
The Universal Machine ^BPRD6
Garden of Souls ^BPRD7
Darkness Calls ^HB8
The Mole ^HB10
The Burial of Katharine Baker ^WF1
Killing Ground ^BPRD8
The Iron Prometheus ^LJ1
Bishop Olek's Devil ^BPRD9
BPRD 1946 ^BPRD9
The Drowning ^AS1
Out of Reach ^BPRD10
The Warning ^BPRD10
The Ectoplasmic Man ^{BPRD: Being Human}
In the Chapel of Moloch ^HB10
They That Go Down to the Sea in Ships ^HB10
The Dragon Pool by Christopher Golden ^(novel)
The Black Goddess ^BPRD11
And What Shall I Find There? ^BPRD13
BPRD 1947 ^BPRD13
Murderous Intent ^WF1
In the Service of Angels ^WF1
The Wild Hunt ^HB9
How Koshchei Became Deathless ^{not collected}
Baba Yaga's Feast ^{not collected}
The Haunted Boy ^AS2
The Abyssal Plain ^AS2
The Devil Does Not Jest ^AS2
King of Fear ^BPRD14
Lost and Gone Forever ^WF2
New World ^HoE1
Gods ^HoE2
The Storm ^HB12
The Fury ^HB12
Monsters ^HoE2
Russia ^HoE3
An Unmarked Grave ^HoE3
The Dead Remembered ^{BPRD: Being Human}
Hellboy in Mexico ^HB11
House of the Living Dead ^{Hellboy: House of the Living Dead}
Hellboy versus the Aztec Mummy ^{not collected}
The Bride of Hell ^HB11
The Whittier Legacy ^HB11
Double Feature of Evil ^HB11
The Sleeping and the Dead ^HB11
Buster Oakley Gets His Wish ^HB11
The Burning Hand ^LJ2
Tony Masso's Finest Hour ^LJ3
Casualties ^{BPRD: Being Human}
The Pickens County Horror ^HoE5
The Long Death ^HoE4
The Devil's Engine ^HoE4
The Transformation of J. H. O'Donnell ^HoE5
Exorcism ^{not collected}
The Prayer of Neferu ^LJ3
Caput Mortuum ^LJ3
BPRD 1948 ^{BPRD: 1948}
Vampire ^{BPRD: Vampire}
Return of the Master ^HoE6
Hellboy in Hell 1-4 ^HBiH1
The Abyss of Time ^HoE5
Wasteland ^HoE7
A Cold Day in Hell ^HoE7
Dark and Terrible ^AS3
New Race of Man ^AS3
Sledgehammer 44 ^SH1
Satan Smells a Rat ^LJ3
A Scent of Lotus ^LJ3
The Midnight Circus ^{Hellboy: The Midnight Circus}
Lake of Fire ^HoE8
The Shape of Things to Come ^AS4
The Land of the Dead ^{not collected}
The Lightning War ^SH1
The Reign of the Black Flame ^HoE9
The Three Gold Whips ^HiH1
Hellboy Gets Married ^{not collected}
The Coffin Man ^{not collected}

--

I haven't yet read these, so I'm not sure what color to code them, but I assume this is the correct order:

??To the Last Man?? ^AS4
??Get The Lobster?? ^LJ4
??Beware the Ape?? ^{not collected}
The Death Card ^{not collected}
??The Garden?? ^AS5
??Mysteries of the Unland?? ^WF3
??The Devil's Wings?? ^HoE10
??The Healer?? ^AS5
??Visions, Dreams, and Fishin'?? ^AS5
??The Broken Equation?? ^HoE10
??Lost Lives?? ^{not collected}
??Sacred Places?? ^AS5
??Grind?? ^HoE10
??Flesh and Stone?? ^HoE11
Hellboy and the BPRD 1952 ^HBBPRD1
??A Darkness So Great?? ^AS6
The Calm Before the Storm ^{not collected}
??The Coffin Man 2: The Rematch?? ^{not collected}
??Frankenstein Underground?? ^FU
??Nowhere, Nothing, Never?? ^HoE12
??Subconscious?? ^{not collected}
The Ogopogo ^{not collected}
??Modern Prometheus?? ^HoE12
??The Shadow over Suwanee?? ^AS7
??A Chain Forged in Life?? ^{not collected}
??The Hounds of Pluto?? ^{not collected}
??End of Days?? ^HoE13
The Phantom Hand ^HBBPRD2
The Kelpie ^HBBPRD2
??Icthyo Sapien?? ^{not collected}
The Witch Tree ^HBBPRD2
Rawhead and Bloody Bones ^HBBPRD2
??The Garden (II)?? ^AS7
??The Exorcist of Vorsk?? ^{not collected}
??The Glass Mantis?? ^{not collected}