En 1976, avec son collègue Kenneth Appel de l'université de l'Illinois à Urbana-Champaign, Haken a résolu un des problèmes les plus célèbres en mathématiques, le théorème des quatre couleurs. Ils démontrèrent que toute carte à deux dimensions peut être coloriée avec quatre couleurs de telle façon que deux pays voisins soient toujours de couleurs différentes.
Haken introduisit plusieurs idées importantes, comme les variétés de Haken(en), la finitude de Kneser-Haken, et un prolongement du travail de Hellmuth Kneser dans une théorie des surfaces normales(en). Une grande part de son travail présente un aspect algorithmique, et il est une des figures influentes de la topologie algorithmique(en). Une de ses contributions clés dans ce domaine est un algorithme pour détecter si un nœud est trivial.
