Our nearest neighbor, Proxima Centauri, hosts a temperate terrestrial planet. We detected in radial velocities evidence of a possible second planet with minimum mass m_c sin i_c = 5.8 ± 1.9M_⊕ and orbital period Pc=5.21−0.22+0.26 years. The analysis of photometric data and spectro-scopic activity diagnostics does not explain the signal in terms of a stellar activity cycle, but follow-up is required in the coming years for confirming its planetary origin. We show that the existence of the planet can be ascertained, and its true mass can be determined with high accuracy, by combining Gaia astrometry and radial velocities. Proxima c could become a prime target for follow-up and characterization with next-generation direct imaging instrumentation due to the large maximum angular separation of ~1 arc second from the parent star. The candidate planet represents a challenge for the models of super-Earth formation and evolution.