Im Mai 2002 wurde er von den Detroit Red Wings unter Vertrag genommen, nachdem er von keinem NHL-Team gedraftet wurde. Die Saison 2002/03 verbrachte er in der East Coast Hockey League bei den Toledo Storm, einem Farmteam der Detroit Red Wings. Ellis zeigte gute Leistungen und wechselte zur Saison 2003/04 zu den Grand Rapids Griffins, dem AHL-Farmteam der Red Wings. Dort zeigte er vor allem seine Qualitäten als Zwei-Wege-Stürmer, der sowohl offensiv als auch defensiv agiert. In jedem Jahr konnte er sich weiter steigern und wurde vor der Saison 2005/06 zum Mannschaftskapitän der Grand Rapids Griffins ernannt. Am 18. Dezember 2006 wurde er zum ersten Mal in den NHL-Kader der Detroit Red Wings berufen und kam in der Saison 2006/07 auf insgesamt 16 Einsätze in der NHL.
Zur Saison 2007/08 gehörte er dann fest zum NHL-Kader der Red Wings, kam aber meistens nur zum Einsatz, wenn ein anderer Spieler verletzt war. Als er im Februar 2008 zu den Griffins in die AHL geschickt werden sollte, wurde er von den Red Wings auf die Waiver-Liste gesetzt und noch bevor die Frist abgelaufen war, nutzten die Los Angeles Kings die Chance und verpflichteten Ellis. In Los Angeles bestritt er noch 19 Ligaspiele, konnte sich dort jedoch nicht etablieren, sodass vor dem Beginn der Saison 2008/09 erneut auf die Waiver-Liste gesetzt wurde und zu den Buffalo Sabres wechselte. Ellis fand sich zwar für einige Partien in der AHL bei den Portland Pirates wieder, spielte aber schließlich den Großteil der Saison in der NHL bei den Sabres.
Die folgenden Saisons waren vom steten Wechsel zwischen AHL und NHL geprägt, ehe die Rochester Americans, das Farmteam der Sabres seit 2011, im Juli 2015 eine erneute Vertragsverlängerung um ein Jahr bekanntgaben, die nur für die AHL Gültigkeit besaß. Nach der Spielzeit, die er damit ausschließlich in Rochester verbrachte, beendete Ellis kurz vor seinem 35. Geburtstag seine aktive Karriere.
Zur Saison 2020/21 kehrte der Kanadier zu den Buffalo Sabres zurück und übernahm dort die Rolle des Directer of Player Development. Bereits im März 2021 übernahm er nach den Entlassungen von Ralph Krueger und Steve Smith die Position des Assistenztrainers, allerdings vorerst interimsweise.
(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)