Seria misji prowadzi zespół Biura do tajemniczych nowych światów, o których od lat spekulowano, ale nigdy wcześniej nie zostały one zweryfikowane. Każdy z tych światów został szczegółowo wymyślony przez del Toro i naszkicowany długo przed rozpoczęciem produkcji. Zadaniem scenografa Stephena Scotta było ożywienie tych rysunków.
Del Toro założył, że ten rozdział przygód Hellboya będzie rozgrywał się nie tylko w bardzo wielu różnych lokalizacjach, ale także w zupełnie nowych sferach. Aby to osiągnąć zdjęcia realizowano zarówno na Węgrzech jak i w Irlandii.
Bez wątpienia, najbardziej ekstrawagancki jest tutaj Troll Market. Zlokalizowany pod Mostem Brooklyńskim i dostępny po przejściu na zaplecze sklepu mięsnego, jest jednym z kilku miejsc, w których dziwolągi nie czują się, jak wyrzutkowie społeczeństwa. Hellboy, Liz, Abe i Johann znajdują Troll Market podążając za radą odczytaną z ust reanimowanej wróżki zębowej, wrednej bestii z olbrzymim apetytem na wapno.
Wstęp na market mają tylko magiczne istoty. "Troll Market jest jak targowisko w Maroku, tylko, że nie ma na nim ludzi," wyjaśnia Ron Perlman. "To pomysł Guillermo del Toro odwiedzającego najbardziej ekstremalne odstępy swojej wyobraźni."
Aby zinterpretować ten świat, scenograf Scott miał trzy miesiące na przekształcenie jaskini o powierzchni 4 000 m2 (używanej uprzednio głównie do hodowli grzybów) w ruchliwe targowisko. Ta podziemna lokalizacja została znaleziona na Węgrzech w odległości 25 mil od Budapesztu, w wiosce Tarnok.
Poza stworzeniem nowych mundurów ludzi pracujących dla Biura, zadaniem autorki kostiumów Sammy Sheldon było upewnienie się, że na tej olbrzymiej przestrzeni nikt nigdy nie pomyli trolli z ludźmi. Zarówno Troll Market jak i okazała Komnata Złotej Armii zostały zaprojektowane w dużym kontraście do świata ludzi na powierzchni. "Świat ludzki jest linearny, z prostymi liniami i ostrymi krawędziami," mówi Scott, "podczas gdy kształty świata pod powierzchnią są zakrzywione i opływowe z mieszanką wpływów indiańskich, marokańskich i północno-afrykańskich."
W Komnacie Złotej Armii mieści się broń masowej zagłady zamówiona przez króla Balora wiele wieków temu. Według del Toro: "Król powiedział, `Chcę armii, która nie potrzebuje jedzenia, snu, picia, ani odpoczynku.' I dlatego skrzaty stworzyły armię złożoną z wysokich na ponad 5 metrów mechanicznych żołnierzy, którzy są maszynami do zabijania. Nie widzą jednak różnicy między mężczyzną, kobietą i dzieckiem - niewinną ofiarą czy żołnierzem." Kiedy władca zdał sobie sprawę z koszmaru swojego żądania zamknął Złotą Armię na wieki, mając nadzieję, że nie wyrządzi już więcej krzywd. Tak było do chwili, kiedy jego syn wyzwolił ponownie jej niszczycielską moc.
Podczas, gdy kamery Navarro pracowały w różnych miejscach Budapesztu, ekipa konstrukcyjna pracowała bez przerwy w Korda Studios, budując nowojorską ulicę. Kiedy 9 czerwca 2007 roku rozpoczęto zdjęcia, Manhattan był niczym oprócz zbiorowiska metalowych rusztowań. W miarę upływu czasu powstały trzy przecznice sklepów, fabryka pakowania mięsa, doki załadunkowe, sklep samochodowy, bank, billboardy, hotel SRO i modna kawiarnia w dzielnicy pakowania mięsa.
Dziwolągi żyją tam, gdzie pracują - w Biurze, którego scenografia została zbudowana w Budapeszcie w halach Korda Studios. Tam też zbudowano osobistą pieczarę Hellboya - pełną zestawów telewizyjnych i kotów.
"Bardzo inspirujące było obserwowanie, jak szkice zostają powoływane do życia podczas zdjęć," mówi producent Levin. "Te fantastyczne światy i istoty zostały bardzo dokładnie zaprojektowane przez Guillermo i wielu artystów pracujących nad filmem Hellboy: Złota Armia. Szczególnie ekscytujące było odnajdowanie szczegółowych szkiców w skomplikowanych obiektach scenograficznych."
