The performance of portable power generation systems is a major limitation on the freedom and amount of utility provided by portable electronic devices. In that respect, fuel cells are a promising alternative to current state-of-the-art batteries as there is the possibility of achieving better performance by efficient design of the underlying chemical processes. The design of micro-fuel cells is a multi-disciplinary problem to meet material, environmental, usage and economical constraints. The focus of this work is the satisfaction of power demand constraints, one of the most important usage constraints. Portable electronic devices operate at varying levels of power demand. A cellular phone at stand-by requires only a fraction of the power that is required during a phone conversation. The power demand of portable computers vary with the current task executed. Efficient design of power generation systems mandates consideration of this ubiquitous variability in demand. Design for only a nominal or worst-case power demand may not be the best design as it may result in unacceptable compromises in portability or degradation of performance at other possible demands. This study comprises a design methodology incorporating varying power demands. The modeling of variability in power demands is discussed. The design problem for a micro-fuel cell in face of variable power demand is formulated as a stochastic program. The scope of the formulation is the determination of optimal design variables and operating conditions for plausible steady-state power demands. Solutions are obtained for a previously published fuel cell model by the authors for various power demand scenarios. It is observed that the incorporation of variability in the power demand results in significantly different fuel cell designs. Finally, additional observations, limitations and possible extensions of the formulation are discussed.