An important direction in the development of energy saving policy is harvesting and conversion into electricity of low-grade waste heat. The present paper is devoted to the improvement of the efficiency of thermo-electrochemical cells based on carbon fiber electrodes and potassium ferri-/ferrocyanide redox electrolyte. The influence of the carbon fiber electrode surface modification (magnetron deposition of silver and titanium or infiltration implantation of nanoscale titanium oxide) on the output power and parameters of the impedance equivalent scheme of a thermo-electrochemical cell has been studied. Two kinds of cell designs (a conventional electrochemical cell with a salt bridge and a coin cell-type body) were investigated. It was found that the nature of the surface modification of electrodes can change the internal resistance of the cell by three orders of magnitude. The dependence of the equivalent scheme parameters and output power density of the thermoelectric cell on the type of electrode materials was presented. It was observed that the maximum power for carbon fiber modified with titanium metal and titanium oxide was 25.2 mW/m2 and the efficiency was 1.37%.