We consider the following class of nonlinear eigenvalue problems: (Σ i=1 m Aipi(λ))v = 0, where A 1,⋯, Am are given n ×n matrices and the functions p1,⋯, pm are assumed to be entire. This does not only include polynomial eigenvalue problems but also eigenvalue problems arising from systems of delay differential equations. Our aim is to compute the ∈-pseudospectral abscissa, i.e., the supremum of the real parts of the points in the ∈-pseudospectrum, which is the complex set obtained by joining all solutions of the eigenvalue problem under perturbations {δA i} i=1 m, of norm at most ∈, of the matrices {A i} i=1 m. Under mild assumptions, guaranteeing the existence of a globally rightmost point of the ∈-pseudospectrum, we prove that it is sufficient to restrict the analysis to rank-one perturbations of the form δA i = β iuv *, where u ∈ ℂ n and v ∈ ℂ n with β i ∈ ℂ for all i. Using this main-and unexpected-result we present new iterative algorithms which require only the computation of the spectral abscissa of a sequence of problems obtained by adding rank one updates to the matrices Ai. These provide lower bounds to the pseudspectral abscissa and in most cases converge to it. A detailed analysis of the convergence of the algorithms is made. Their applicability and properties are illustrated by means of the delay and polynomial eigenvalue problem.