New electronic phases have been identified and placed in the (T,H) phase diagram of metallic NaxCoO2. At low Na-content (x = 0.36), the magnetic susceptibility diverges with a power law T^(-n), n<1, and shows (T,H) scaling, indicating the proximity to a magnetic quantum phase transition. At high Na contents (x = 0.6) the mass of the quasiparticles does never diverge, but renormalizes and becomes strongly field dependent at low temperatures, forming a heavy Fermi-Liquid. Our results make superconducting NaxCoO2 a clear candidate for magnetically mediated pairing.