1988 übernahm er sein ehemaliges Juniorenteam, die Sault Ste. Marie Greyhounds als Trainer. Dreimal in Folge führte er das Team in die Endrunde des Memorial Cups. 1993 gewannen die Greyhounds den Titel. 1994 wechselte er als Assistenztrainer zu den Hartford Whalers. Nach einem Jahr der wechselte er als Cheftrainer zu den Buffalo Sabres. Dort war er für zwei Jahre sehr erfolgreich, überwarf sich aber mit dem Startorhüter Dominik Hašek und General Manager John Muckler. Dies entzog die Basis einer weiteren Zusammenarbeit und so wurde er von Lindy Ruff abgelöst.
Erst 2005 kehrte er zum Eishockey zurück. Er trainierte die Moncton Wildcats in der Québec Major Junior Hockey League in dieser Zeit musste er sich mit rassistischen Übergriffen bei einem Spiel gegen die Chicoutimi Sagueneens auseinandersetzen. Die New York Islanders versuchten ihn während der Saison zu verpflichten, doch Nolan wollte seinen Vertrag in Moncton erfüllen. Nach Ende der Saison einigte er sich mit den Islanders und übernahm das Team zur Saison 2006/07. Nachdem die Islanders lange Zeit außerhalb der Playoff-Plätze rangierten, gelang ihnen die Qualifikation im letzten Saisonspiel schließlich doch, scheiterten aber schon in der ersten Runde. In der Saison 2007/08 verpassten sie jedoch die Playoffs und im Sommer 2008 trennten sich das Team von Nolan. Nach einer Zeit bei den Rochester Americans trainiert er zwischen 2011 und 2014 die lettischen Eishockeynationalmannschaft.[3] Ab dem 13. November 2013 trainierte er außerdem wieder die Buffalo Sabres.[4] Die Sabres entließen ihn nach der Saison 2014/15, die die Mannschaft auf dem letzten Rang beendete.