We present a new algorithm for penalized-likelihood emission image reconstruction. The algorithm monotonically increases the objective function, converges globally to the unique maximizer, and easily accommodates the nonnegativity constraint and nonquadratic but convex penalty functions. The algorithm is based on ﬁnding paraboloidal surrogate functions for the log-likelihood at each iteration: quadratic functions that are tangent to the log-likelihood at the current image estimate, and lie below the log-likelihood over the entire nonnegative orthant. These conditions ensure monotonicity. The paraboloidal surrogates are maximized easily using existing algorithms such as coordinate ascent. Simulation results show that the proposed algorithm converges faster than the SAGE algorithm, yet the new algorithm is somewhat easier to implement.