Zur Saison 1988/89 wechselte der Kanadier schließlich in die Organisation der New Jersey Devils, verbrachte die gesamte Saison aber bei deren Farmteam, den Utica Devils, in der American Hockey League (AHL). Erst im Verlauf des folgenden Spieljahres debütierte das Talent in der NHL, kam dort zu 19 Einsätzen für die Devils sowie 39 weiteren in der AHL. In der Spielzeiten 1990/91 und 1991/92 beschränkten sich seine NHL-Einsatzzeiten nur noch auf eine deutlich einstellige Anzahl von Spielen. Lediglich in der AHL-Saison 1990/91 wusste er in Utica mit 96 Scorerpunkten zu überzeugen.
Folglich waren die Devils nach dem vierten Profijahr ihrer hohen Draftwahl unzufrieden und transferierten ihn im September 1992 zu den neu in die Liga aufgenommenen Ottawa Senators. Dort zeichnete Brady für das erste Tor der Franchise-Geschichte verantwortlich und gehörte über weite Teile der Saison 1992/93 zum NHL-Stammpersonal des Teams. Dennoch wechselte er im Sommer 1993 als Free Agent in die Organisation der Dallas Stars. Für die Stars selbst absolvierte er jedoch nur insgesamt fünf Spiele. Stattdessen verbrachte er die folgenden vier Jahre in deren Farmteam, den Kalamazoo Wings, in der International Hockey League (IHL). Zur Spielzeit 1995/96 benannte sich das Team in Michigan K-Wings um.
Auch in der kehrte Brady nicht mehr in die NHL zurück, sondern verblieb in der IHL. Dort lief er zwischen 1997 und 2001 noch für die Houston Aeros, Manitoba Moose, Utah Grizzlies und Chicago Wolves auf, ehe er seine Karriere im Alter von 33 Jahren für beendet erklärte. In der Saison 2002/03 versuchte sich Brady für eine Spielzeit als Assistenztrainer bei den Prince Albert Raiders aus der WHL.
(Legende zur Spielerstatistik: Sp oder GP= absolvierte Spiele; T oder G= erzielte Tore; V oder A= erzielte Assists; Pkt oder Pts= erzielte Scorerpunkte; SM oder PIM= erhaltene Strafminuten; +/−= Plus/Minus-Bilanz; PP= erzielte Überzahltore; SH= erzielte Unterzahltore; GW= erzielte Siegtore; 1Play-downs/Relegation; Kursiv: Statistik nicht vollständig)