Iterative methods of Laguerre’s type for the simultaneous inclusion of all zeros of a polynomial are proposed. Using Newton’s and Halley’s corrections, the order of convergence of the basic method is increased from 4 to 5 and 6, respectively. Further improvements are achieved by the Gauss-Seidel approach. Using the concept of the $R$-order of convergence of mutually dependent sequences, we present the convergence analysis of total-step and single-step methods. The suggested algorithms possess a great computational efficiency since the increase of the convergence rate is attained without additional calculations. The case of multiple zeros is also studied. Two numerical examples are given to demonstrate the convergence properties of the proposed methods.