At P = 1 atm, the only stable compounds in the Na-Bi binary system are Na3Bi and NaBi, which have recently been discovered to exhibit intriguing electronic behaviour as a 3D topological Dirac semimetal and a topological metal, respectively. By means of first-principles calculations coupled with evolutionary structural searches, we have systematically investigated the phase stabilities, the crystal structures and the corresponding electronic properties of the binary Na-Bi system. At ambient pressure, our calculations have reproduced well the experimentally observed compositions and structures of Na3Bi and NaBi. At high pressures, we have found that Na3Bi is transformed from the ground-state hexagonal hP24 phase to a cubic cF16 phase above 0.8 GPa, confirming previous experiments, and then to a conventional band-insulating oC16 phase above 118 GPa. The cubic cF16 phase would exhibit novel topological band ordering similar to that in HgTe. The topological metal NaBi has also been found to undergo a structural phase transition from the ambient tetragonal tP2 to a cubic cP2 structure above 36 GPa. Four compounds never before reported, Na6Bi, Na4Bi, Na2Bi and NaBi2, with new compositions, have been predicted to be experimentally synthesizable over a wide range of pressures starting at 142.5 GPa, 105 GPa, 38 GPa and 171 GPa, respectively. Moreover, a common charge transfer from Na to Bi has been observed for all compounds, but substantial interstitial charge localization in Na atomic cages has been noticed only in two compounds, Na6Bi and Na4Bi, and may be associated with close-packed Na environments.