Official locations

SoulGold Legendary Locations

Locations below are from the official legendary guide. The README also states that some legendary bosses have multiple HP bars and are guaranteed to be catchable with any ball after defeat.

SoulGold wild Palkia encounter in a legendary arena — Legendary hunts combine story flags, field tools, puzzle solutions, and postgame facilities.

Story and Johto encounters

Pokémon	Location / trigger	Important detail
Raikou, Entei, Suicune	Roam after the Burned Tower event	Shininess is rolled at release, not on each later encounter.
Lugia	Silver Wing after the Goldenrod takeover	If Rainbow Wing was chosen, speak with the Director after the Elite Four.
Ho-Oh	Rainbow Wing after the Goldenrod takeover	If Silver Wing was chosen, use the Director’s post-Elite-Four route.
Shadow Lugia	Abandoned Rocket Warehouse south of Johto	Surf south from Route 33 as far as you can, then take the right turn. Complete the warehouse puzzles for the Dark Crystal, then bring it to the regular Lugia encounter.
Celebi	Eight Ruins of Alph puzzles, Kurt, Ilex shrine	Four slider puzzles and four wall puzzles are required; the GS Ball comes from the B1F passage.

Birds, Mew, and Mewtwo

Articuno: Snowtop Mountain, requiring Rock Climb.
Zapdos: the top of Olivine Lighthouse after the eighth badge.
Moltres: Victory Road.
Galarian birds: Route 50 Battle Café, five points per bird.
Mewtwo: Nameless Dungeon at Kitakami Border after the Elite Four; Rock Climb is required.
Mew: after eight badges, defeat Blaine at Olivine port to unlock Faraway Island.

Regis and postgame gates

Group	Where	Required condition or party check
Regirock	Vajra Desert West	Braille puzzle; bring Tyranitar.
Regice	Snowtop Mountain	Braille puzzle; bring Baxcalibur.
Registeel	Railway Cave	Braille puzzle; bring Kommo-o.
Regigigas	Mt. Silver back room	Bring all three Regis.
Latias / Latios	Vajra Desert East temple	Postgame access.
Kyogre / Groudon	Dive spots south of Route 33 / Route 50	The legendary guide says your rival gives Dive after the Darkrai event; the FAQ describes it as the end of a rival questline that starts after the Mt. Silver event. Both point to the rival’s house.
Rayquaza	Embedded Tower	Become Champion and defeat Steven in the Kitakami house.
Uxie / Mesprit / Azelf	Route 30 / Route 47 / Mahogany Town	Rock Climb spots.
Heatran	Mt. Mortar depths	Waterfall and Rock Climb.
Cresselia	Lake of Rage quest	Complete the Mt. Silver rival story, then speak with the rival and Hidden Power Dude.

Multi-step legendary chains

Dialga, Palkia, Giratina: obtain Hoopa, solve all eight Ruins of Alph puzzles, then revisit Celebi’s secret room with Hoopa in the party.
Darkrai: obtain Cresselia, show it to your rival, enter the Cherrygrove inn, and solve the Moon Key, bedroom, papers, trophy, telephone, piano, and safe sequence.
Primal Dialga: bring Grovyle, Dusknoir, and Celebi to the Time Gear on Spear Pillar Summit.
Rayquaza: finish the Champion/Steven trigger before searching the Embedded Tower.

Arceus: the Pokédex reward

Arceus is not a wild encounter. Professor Oak gives it to you in Radio Tower 2F once the Pokédex is complete, which means catching all608 non-legendary, non-mythical Pokémon. Legendaries and mythicals do not count toward that number. Use DexNav, Hidden Grottos, the Safari Zone (its second area opens before Ice Path and the third after Tohjo Falls), and in-game trades to fill the gaps, and check the Pokédexfor encounter locations.

Paradox Pokémon

Pokémon	How to get it
Most Paradox Pokémon	Explore Meteor Island in South Johto.
Walking Wake, Gouging Fire, Raging Bolt	Register every past Paradox Pokémon, then use the Unown wall; bring Entei, Raikou, and Suicune to their walls in the next room.
Iron Leaves, Iron Boulder, Iron Crown	Register every future Paradox Pokémon, then use the back wall; bring Virizion, Terrakion, and Cobalion to their walls.
Koraidon / Miraidon	25 points each at the Route 50 Battle Café after obtaining all other Paradox Pokémon.

Changed in v1.2: Paradox “legendaries” now respawn after a title defense, and they are not required for Pokédex completion. If you missed one, beat the title defense and return.

Other legendaries and mythicals

Pokémon	Where / trigger
Jirachi	Complete the rival story at Mt. Silver.
Phione, Manaphy	Fish with a Good or Super Rod in the South Johto Sea area where only Shellos and Gastrodon appear; Phione evolves into Manaphy at level 58.
Shaymin	Dream Garden, reached from Tohjo Falls with Rock Climb.
Victini	After becoming Champion, talk to the old woman in the Kitakami Border house and beat every Gym Leader rematch.
Cobalion / Terrakion / Virizion	Railway Cave (Route 33 exit) and Dark Cave North after becoming Champion; Virizion is on Route 50.
Forces of Nature, Tapus	5 points each at the Battle Café; the first Force purchase includes the Reveal Glass.
Meloetta	Ecruteak Dance Theater after becoming Champion.
Genesect	Abandoned Rocket Warehouse after becoming Champion.
Diancie	Beat every regular Battle Café opponent once, then talk to the café owner.
Hoopa	Complete the Rinto Village Tinkaton trade, then explore the depths of Vajra Pyramid after becoming Champion.
Magearna	After becoming Champion, win 25 Rocket Arcade rounds for the burglar’s key to the top floor of Goldenrod Apartment. Original Color Magearna is the 100-trophy reward.
Marshadow	After the eighth badge, return to Elder Li in Sprout Tower, then explore the basement.
Zeraora	Reach a 30-win streak in the Battle Tower.
Meltan	Trade Tinkaton in Rinto Village.
Kubfu	Rock Climb cave in Blackthorn City; evolution scrolls are sold at the Rocket Arcade.
Bloodmoon Ursaluna	Find the Black Mirror on Kitakami Mountain, then follow the Murkrow in the Lost Woods.
Eternal Floette, Poipole, Zarude	Trophy rewards at 60, 45, and 75 trophies; see achievements.

Capture rule: the README says some legendary boss fights use multiple HP bars; after defeating those bosses, the catch is guaranteed with any ball. Save before the encounter anyway, especially if you are also hunting a shiny.

Puzzle solutions (Celebi’s Ruins of Alph panels, the Darkrai inn, the Paradox walls, Heatran and Kubfu caves) are in the official legendary guide in the sources below. Use the Pokédex for species data and the shiny guide if you want to soft-reset a legendary.