The optimization of the design of a packed-bed thermal energy storage unit is presented. A one-dimensional, transient, two-phase model is chosen for the packed bed which assumes uniformity at each cross section within the packing. The governing equations for the time dependent temperature distributions in both the solid and fluid phases are solved using a fully implicit formulation. The accuracy of the numerical method is demonstrated by comparison with experimental measurements of temperature distribution in a randomly packed bed of uniform spheres. The goal of the optimization is to achieve maximum utilization of the thermal energy storage and recovery capabilities of the storage medium for a given set of operating conditions. The optimum combination of bed length, size of the packing particles, and relative size of the bed cross section to the particle diameter is determined, subject to constraints on the maximum allowable pressure drop across the packing, the maximum outlet fluid temperature, and the total amount of supplied energy. The thermodynamic availability is examined as the measure of storage utilization. The monotinicity method is utilized for the optimization process. This method identifies a global optimum without any special computations, and prevents acceptance of false optimum solutions, as could be generated by numerical techniques. The results of the study provide guidelines for choosing the size of the packing and the packing particle subject to the constraints for a practical operating system.