Carbon based bipolar plates and O-rings are key components and account for most weight and about half cost of a polymer electrolyte membrane (PEM) fuel cell stack. One function of bipolar plates is to channel fluids through a PEM fuel cell stack, and O-rings are used to avoid leaks of these fluids. However, inappropriate designs of O-ring shapes cannot seal the fluids in operation, and may induce the failure of bipolar plates in the assembly process. In this paper, we use an optimum design program and a commercial finite element analysis (FEA) software to find the best shape of O-rings for a PEM fuel cell stack whose bipolar plates are made of carbon. First of all, the behaviors of the original O-ring shape are determined by FEA with a two-dimension structural model. Non-linear material properties are also considered in the structural analysis. According to the results, the original O-ring design has drawbacks and might damage the carbon bipolar plates during the assembling. Therefore, an optimum design problem is formulated to improve the performance of O-rings. The objective of this optimum design program is to find a set of parameters to minimize the bipolar plate stress. The constraints include geometrical limit, functional requirement, and the structural safety of bipolar plates. Finally, a structural optimization program integrated with FEA software and an optimum design program is developed for this optimum design problem. Approximation concepts are also implemented in the optimum search process to reduce the computing time. The results of the optimization promote the stack structure.