Re-design of a given antenna structure for various substrates is a practically important issue yet non trivial, particularly for wideband and ultra-wideband antennas. In this work, a technique for expedited redesign of ultra-wideband antennas for various substrates is presented. The proposed approach is based on inverse surrogate modeling with the scaling model constructed for several reference designs that are optimized for selected values of the substrate permittivity. The surrogate is set up at the level of coarse-discretization EM simulation model of the antenna and, subsequently, corrected to provide prediction at the high-fidelity EM model level. The dimensions of the antenna scaled to any substrate permittivity within the region of validity of the surrogate are obtained instantly, without any additional EM simulation necessary. The proposed approach is demonstrated using an ultra-wideband monopole with the permittivity scaling range from 2.2 to 4.5. Numerical validation is supported by physical measurements of the fabricated prototypes of the re-designed antennas.