HeartGold has two separate Pokédexes to complete: the Johto Pokédex and the National Pokédex. All Pokémon from the Johto Pokédex, except for Mew and Celebi (which were only available via long-defunct events), are available between HeartGold and SoulSilver. Not all Pokémon from the National Pokédex are available, 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.