All three legendary birds are available in Fire Red and Leaf Green before or shortly after the Elite Four. Step-by-step locations and catching walkthroughs for each.
The Freeze Pokémon — found deep in the Seafoam Islands. Requires solving a boulder puzzle to reach. Ice/Flying type with high Special Defense.
Seafoam Islands require both Surf (HM03 — Safari Zone) and Strength (HM04 — Fuchsia City warden). Without both HMs, you can't reach Articuno. Make sure your party has Pokémon that can use both.
Surf west from Cinnabar Island (or east from Fuchsia City) along Route 20. You'll reach two islands in the middle of the sea — this is the Seafoam Islands cave entrance. Enter from either island's entrance.
The cave has a strong underwater current that prevents you from Surfing to Articuno. To slow the current, you need to push four boulders into holes using Strength:
Navigate to the lowest floor (B4F) and Surf north through the now-still water. Articuno is at the far end of the chamber. Save your game, then step up to trigger the battle. It's level 50 with Powder Snow, Mist, Ice Beam, and Agility.
Don't use your Master Ball here! Articuno is challenging but very catchable with 20 Ultra Balls + sleep. Save your Master Ball for the roaming legendary dogs, which are far harder to catch.
The Electric Pokémon — the easiest of the three birds to reach. No puzzle required, just Surf to the Power Plant on Route 10.
You need Surf (HM03 from the Safari Zone) to access the Power Plant. Without it, you can't cross the water to the building's entrance.
Route 10 runs south from the Rock Tunnel entrance. Use Surf on the river that flows through Route 10 — ride the current east toward the Power Plant building, a large industrial structure on the water's edge.
The Power Plant is a single-floor building filled with wild Electric Pokémon (Magnemite, Voltorb, Electabuzz) and item balls — some of which are disguised Voltorbs. Navigate to the far end of the building where Zapdos waits.
Zapdos is at the dead end of the Power Plant. Save before approaching it. At level 50, it uses Thunder Wave, ThunderShock, DrillPeck, and Thunder. Its Electric moves can paralyze you, so bring Paralyz Heals.
The Flame Pokémon — moved from Victory Road to Mt. Ember on One Island in FRLG. Requires progressing through the Sevii Islands questline to access.
FRLG Change: In the original Red/Blue, Moltres was in Victory Road. In Fire Red and Leaf Green, it was relocated to Mt. Ember on One Island in the Sevii Islands. Don't look for it at Victory Road — it's not there.
After obtaining the first two Badges and talking to Bill in Cerulean City, you'll be invited to the Sevii Islands. The ferry from Vermilion takes you to One Island (also called Knot Island). This is available early in the game.
On your first visit to One Island, Bill's friend Celio asks you to find the Ruby stone on Mt. Ember. Go north through One Island town to reach Mt. Ember's base. You'll need to defeat two Team Rocket grunts who are guarding a hidden cave entrance near the summit.
After completing the initial questline and having Strength, return to Mt. Ember. The path to the summit requires using Strength to push boulders. Work your way up through the rocky interior of the mountain toward the peak.
Moltres waits at the very top of Mt. Ember. Save before engaging. At level 50, it uses FireSpin, Agility, Ember, and Leer. Fire Spin can trap you for several turns — have a Water or Rock type ready to take hits.