This paper introduces the concept of pseudospectra as a generalized tool for uncertainty quantification and propagation in structural dynamics. Different types of pseudospectra of matrices and matrix polynomials are explained. Particular emphasis is given to structured pseudospectra for matrix polynomials, which offer a deterministic way of dealing with uncertainties for structural dynamic systems. The pseudospectra analysis is compared with the results from Monte Carlo simulations of uncertain discrete systems. Two illustrative example problems, one with probabilistic uncertainty with various types of statistical distributions and the other with interval type of uncertainty, are studied in details. Excellent agreement is found between the pseudospectra results and Monte Carlo simulation results.