Non-stationary random vibration of linear structures with uncertain parameters is investigated in this paper. A time-domain explicit formulation method is first presented for dynamic response analysis of deterministic structures subjected to non-stationary random excitations. The method is then employed to predict the random responses of a structure with given values of structural parameters, which are used to fit the conditional expectations of responses with relation to the structural random parameters by the response surface technique. Based on the total expectation theorem, the known conditional expectations are averaged to yield the random responses of stochastic structures as the total expectations. A numerical example involving a frame structure is investigated to illustrate the effectiveness of the present approach by comparison with the power spectrum method and the Monte Carlo simulation method. The proposed method is also applied to non-stationary random seismic analysis of a practical arch bridge with structural uncertainties, indicating the feasibility of the present approach for analysis of complex structures.