In practical engineering, the uncertainties commonly exist in the design process of composite structures due to the dispersion of composite materials. This paper proposes an uncertain optimization method based on interval model updating technique and non-probabilistic reliability (NPR) theory. A novel interval model updating method is firstly established by modifying the deterministic constraint condition parameters, which retains the quantification results of the material parameters and has a convinced updating model. In the design section, a new two-step optimization process for composite structures, which combines NPR method and progressive failure theory, is presented based on the updated simulation model. The traditional composite structural design method (safety factor based method) is also introduced to be compared. The NPR based optimization can optimize the nominal value and deviation of the structural response simultaneously, and will achieve a more significant weight reduction effect. A complete process including the uncertainty quantification, interval model updating, NPR based optimization and experimental verification for a composite stiffened plate under the compressive and shear load conditions were performed to verify the effectiveness of the proposed methodology.