Example of a conjecture/theorem which required an entirely new idea to prove

Solution 1:

Does Euler's solution of the Seven Bridges of Königsberg problem (considered by some the first theorem of graph theory) count?

Solution 2:

From Morris Kline's Mathematical Thought from Ancient to Modern Times, Vol III, pg. 970:

In the paper containing George Cantor's final answer to the question of whether a function can have two different trigonometric series representations in the interval $[-\pi,\pi]$, Cantor "laid the foundation of the theory of point sets".

Solution 3:

The Four Color Theorem. Who ever back then thought that we might use a computer to help us proving something...