Inspired by gradient structures in the nature, Gradient Nanostructured (GNS) metals have emerged as a new class of materials with tunable microstructures. GNS metals can exhibit unique combinations of material properties in terms of ultrahigh strength, good tensile ductility and enhanced strain hardening, superior fatigue and wear resistance. However, it is still challenging to fully understand the fundamental gradient structure-property relationship, which hinders the rational design of GNS metals with optimized target properties. In this paper, we developed an adaptive design framework based on simulation-based surrogate modeling to investigate how the grain size gradient and twin thickness gradient affect the strength of GNS metals. The Gaussian Process (GP) based surrogate modeling technique with adaptive sequential sampling is employed for the development of surrogate models for the gradient structure-property relationship. The proposed adaptive design integrates physics-based simulation, surrogate modeling, uncertainty quantification and optimization, which can efficiently explore the design space and identify the optimized design of GNS metals with maximum strength using limited sampling data generated from high fidelity but computational expensive physics-based simulations.