We present a complete methodology to consistently estimate redox potentials strictly from first-principles, without any experimental input. The methodology is based on (i) ab initio molecular dynamics (MD) simulations, (ii) all-atom explicit solvation, (iii) the two-phase thermodynamic (2PT) model, and (iv) the use of electrostatic potentials as references for the absolute electrochemical scale. We apply the approach presented to compute reduction potentials of the following redox couples: Cr2+/3+, V2+/3+, Ru(NH3)62+/3+, Sn2+/4+, Cu1+/2+, FcMeOH0/1+, and Fe2+/3+ (in aqueous solution) and Fc0/1+ (in acetonitrile). We argue that fully quantum-mechanical simulations are required to correctly model the intricate dynamical effects of the charged complexes on the surrounding solvent molecules within the solvation shell. Using the proposed methodology allows for a computationally efficient and statistically stable approach to compute free energy differences, yielding excellent agreement between our computed redox potentials and the experimental references. The root-mean-square deviation with respect to experiment for the aqueous test set and the two exchange-correlation density functionals used, PBE and PBE with van der Waals corrections, are 0.659 and 0.457 V, respectively. At this level of theory, depending on the functional employed, its ability to correctly describe each particular molecular complex seems to be the factor limiting the accuracy of the calculations.