New algorithms are presented for computing annihilating polynomials of Toeplitz, Hankel, and more generally Toeplitz+Hankel-like matrices over a field. Our approach follows works on Coppersmith's block Wiedemann method with structured projections, which have been recently successfully applied for computing the bivariate resultant. A first baby steps/giant steps approach --directly derived using known techniques on structured matrices-- gives a randomized Monte Carlo algorithm for the minimal polynomial of an (n x n) Toeplitz or Hankel-like matrix of displacement rank α using(Õnw-c(w) Õ c(w)) arithmetic operations, where (w) is the exponent of matrix multiplication and (c(2.373) = 0.523) for the best known value of (w). For generic Toeplitz+Hankel-like matrices a second algorithm computes the characteristic polynomial; in particular, when the displacement rank is considered constant, its cost is (Õn2-1/w). Previous algorithms required (O(n2) operations while the exponents presented here are respectively less than 1.86 and 1.58 with the best known estimate for (w).