The optimization of the design of a solid sensible heat storage unit initially at a uniform-temperature is presented. The storage unit is composed of a number of rectangular cross-sectional channels for the flowing fluid, connected in parallel and separated by the heat storage material. The complex method for constrained nonlinear optimization as presented by M. J. Box is utilized, with some modifications. The design optimization is based upon achieving maximum utilization of the heat storage or removal capabilities of the material for a given set of operating conditions. This is achieved by varying the storage unit’s geometry while placing constraints on the maximum and minimum length of the unit, fluid channel size, storage material thickness, maximum and minimum outlet fluid temperature, and the minimum amount of heat to be stored.