The search for clean and renewable sources of energy represents one of the most vital challenges facing us today. Solid oxide fuel cells (SOFCs) are among the most promising technologies for a clean and secure energy future due to their high energy efficiency and excellent fuel flexibility (e.g., direct utilization of hydrocarbons or renewable fuels). To make SOFCs economically competitive, however, development of new materials for low-temperature operation is essential. Here we report our results on a computational study to achieve rational design of SOFC cathodes with fast oxygen reduction kinetics and rapid ionic transport. Results suggest that surface catalytic properties are strongly correlated with the bulk transport properties in several material systems with the formula of La0.5Sr0.5BO2.75 (where B = Cr, Mn, Fe, or Co). The predictions seem to agree qualitatively with available experimental results on these materials. This computational screening technique may guide us to search for high-efficiency cathode materials for a new generation of SOFCs.