HeartGold has two separate Pokédexes to complete: the Johto Pokédex and the National Pokédex. The Johto Pokédex corresponds to the Dex in the original Gold, Silver, and Crystal games (Pokémon 1-251), with the addition of Tangrowth, Mamoswine, Lickilicky, Yanmega, and Ambipom. The National Pokédex consists of the Johto Pokédex plus the Pokémon introduced in Ruby, Sapphire, & Emerald and Diamond, Pearl, & Platinum (Pokémon 252-493). All Pokémon from the Johto Pokédex, except for the event-exclusive Mew and Celebi, are available between HeartGold and SoulSilver. Most of the remaining Pokémon are also available, but there are a few exceptions, making it impossible to complete the National Pokédex with access to only those two games. This page will show the maximum number of Pokémon that can be obtained.
The maximum number of Pokémon you can get this way is 428, or 449 with access to the Pokéwalker.
The following version-exclusive Pokémon have to be traded from SoulSilver:
Trading Groudon from SoulSilver is additionally the only way to get the Rayquaza that appears at the Embedded Tower.
Several Pokémon are mutually exclusive, meaning that if you get one species, you cannot get at least one other species. The list of mutually exclusive species is below.
You will need at minimum three separate save files to get each of these starters. Each save file will pick three different starters from this list, and they can be bred and traded as needed.
17 Pokémon evolve by trading: Golem, Machamp, Alakazam, Gengar, Politoed, Slowking, Steelix, Scizor, Kingdra, Porygon2, Huntail, Gorebyss, Rhyperior, Electivire, Magmortar, Porygon-Z, and Dusknoir. The easiest way to get data for them is to trade them to another game and immediately trade the newly-evolved Pokémon back.
You will need two King's Rocks, two Metal Coats, one Dragon Scale, one Up-Grade, one DeepSeaTooth, one DeepSeaScale, one Protector, one Electirizer, one Magmarizer, one Dubious Disc, and one Reaper Cloth to evolve Politoed, Slowking, Steelix, Scizor, Kingdra, Porygon2, Huntail, Gorebyss, Rhyperior, Electivire, Magmortar, Porygon-Z, and Dusknoir.
If you have access to the Pokéwalker, you can obtain the following Pokémon: Skitty, Delcatty, Carvanha, Sharpedo, Wailmer, Wailord, Feebas, Milotic, Castform, Kecleon, Tropius, Snorunt, Glalie, Froslass, Shellos, Gastrodon (West Sea only), Spiritomb, Finneon, Lumineon, Snover, and Abomasnow.
East Sea Shellos and Gastrodon must still be traded from Diamond, Pearl, or Platinum.
The remaining Pokémon are obtainable only in Diamond, Pearl, Platinum, Ruby, Sapphire, Emerald, or defunct events.
If the player does not have access to the Pokéwalker, this total is instead 65.