Fuel cells (FC) are considered the most efficient chemical-to-electrical energy (CEE) conversion devices because, in contrast to conventional power generation systems, they are not limited by Carnot efficiency. Most R&D efforts in this area are focused on hydrogen-powered FC. However, the overall CEE efficiency of a combined reformer-FC system is relatively low (35-40%) mainly due to a moderate practical efficiency of hydrogen FC (45-50%) and loses during the reforming stage. The objective of this work is to develop a highly-efficient power generation system that combines hydrogen and direct-carbon (DC) FC. The unique feature of DC-FC is that its theoretical CEE efficiency is almost 100% (because entropy of carbon oxidation reaction is close to zero). CEE efficiencies of 80% have been demonstrated on the laboratory scale DC-FC. According to a technical approach proposed in this paper, hydrocarbon (e.g., natural gas) is thermo-catalytically dissociated to hydrogen and carbon. Hydrogen is used in either PEM or solid oxide FC, whereas, carbon is fed to DC-FC. The experimental data on testing methane dissociation reactor coupled with PEM FC are presented in this paper. The overall methane-to-electricity conversion efficiency of the system was estimated at 70-75%, which is twice as high as that of advanced fossil-based power plants (thus, the carbon dioxide yield per kW of electricity would be reduced by half). Advantageously, DC-FC produces practically pure carbon dioxide, which obviates the need for its capture and makes its subsequent sequestration relatively easy.