Another example from logic is Gentzen's consistency proof for Peano
arithmetic by transfinite induction up to $\varepsilon_0$, which I 
think was completely unexpected, and unprecedented.