The alternating sign matrix conjecture was first proved by Doron Zeilberger; the proof was enormously computational. Later, Greg Kuperberg gave a much shorter proof using results from statistical mechanics. Kuperberg's proof is still not trivial, but it is more conceptual.

(It's worth mentioning that very recently, Fischer and Konvalinka have announced a bijective proof of the same theorem, which is pleasing to a combinatorialist, but far from trivial, and hence probably not an answer to the question.)