We analyse an extension of Shoup's (Inform. Process. Lett. 33 (1990) 261–267) deterministic algorithm for factoring polynomials over finite prime fields to arbitrary finite fields. In particular, we prove the existence of a deterministic algorithm which completely factors all monic polynomials of degree n over Fq, q odd, except possibly O(n2 log2 q/q) polynomials, using O(n2+ log2q) arithmetical operations in Fq.