Driven by the search for the highest theoretical efficiency, in the latest years several studies investigated the integration of high temperature fuel cells in natural gas fired power plants, where fuel cells are integrated with simple or modified Brayton cycles and/or with additional bottoming cycles, and CO2 can be separated via chemical or physical separation, oxy-combustion and cryogenic methods. Focusing on Solid Oxide Fuel Cells (SOFC) and following a comprehensive review and analysis of possible plant configurations, this work investigates their theoretical potential efficiency and proposes two ultra-high efficiency plant configurations based on advanced intermediate-temperature SOFCs integrated with a steam turbine or gas turbine cycle. The SOFC works at atmospheric or pressurized conditions and the resulting power plant exceeds 78% LHV efficiency without CO2 capture (as discussed in part A of the work) and 70% LHV efficiency with substantial CO2 capture (part B). The power plants are simulated at the 100 MW scale with a complete set of realistic assumptions about fuel cell (FC) performance, plant components and auxiliaries, presenting detailed energy and material balances together with a second law analysis.