Nacido en Farmersville, Texas y criado en los suburbios de Dallas, Ellis escuchó por primera vez la guitarra eléctrica interpretada por George Barnes en un programa de radio. Se dice que esta experiencia lo inspiró a tomar la guitarra. Se convirtió en experto en el instrumento cuando ingresó en la Universidad Estatal del Norte de Texas. Ellis se especializó en música, pero debido a que aún no había un programa de guitarra en ese momento, estudió el bajo de cuerda. Desafortunadamente, debido a la falta de fondos, sus días universitarios fueron de corta duración. En 1941, Ellis abandonó la universidad y realizó una gira de seis meses con una banda de la Universidad de Kansas.

En 1943, se unió a Glen Gray y la Orquesta Casa Loma y fue con la banda de Gray que obtuvo su primer reconocimiento en las revistas de jazz. Después de la banda de Gray, Ellis se unió a la banda de Jimmy Dorsey donde tocó algunos de sus primeros solos grabados. Ellis se quedó con Dorsey hasta 1947, viajando y grabando extensamente, y tocando en salones de baile y teatros.

Luego vino un episodio que cambiaría la carrera de Ellis para siempre. Según dijo el pianista Lou Carter al periodista Robert Dupuis en una entrevista en 1996, "La banda de Dorsey tenía un paréntesis de seis semanas en el programa de actuaciones. Los tres habíamos tocado juntos con la big band. John Frigo, que ya había dejado la banda conocía al dueño del Hotel Peter Stuyvesant en Buffalo. Fuimos allí y nos quedamos seis meses. Y así nació el grupo Soft Winds ". Junto con Frigo y Lou Carter, Ellis escribió el estándar clásico de jazz "Detour Ahead".

El grupo Soft Winds fue creado a imagen del Nat King Cole Trio. Permanecieron juntos hasta 1952. Ellis luego se unió al Oscar Peterson Trio (reemplazando a Barney Kessel) en 1953, formando a lo que Scott Yanow más tarde se referiría como "uno de los tríos de piano, guitarra y bajo más memorables en la historia del jazz".3​

Ellis se hizo prominente después de actuar con el Oscar Peterson Trio de 1953 a 1958 junto con el pianista Peterson y el bajista Ray Brown. Era un miembro del trío un tanto controvertido, porque era la única persona blanca del grupo en un momento en que el racismo todavía estaba muy extendido.

Además de su gran trabajo en vivo y grabado con el Oscar Peterson Trio, esta unidad generalmente con la adición de un baterista, sirvió como la virtual "sección de ritmo de la casa" para Verve Records de Norman Granz, apoyando los gustos de los tenores Ben Webster y Stan Getz, así como los trompetistas Dizzy Gillespie, Roy Eldridge y Sweets Edison y otras leyendas del jazz. Con el baterista Buddy Rich, también fueron la banda de acompañamiento de los populares álbumes de "regreso" del dúo de Ella Fitzgerald y Louis Armstrong.

El trío fue uno de los pilares de los conciertos de Jazz At The Philarmonic de Granz mientras recorrían el mundo del jazz, viajando casi constantemente por Estados Unidos y Europa. Ellis dejó el Peterson Trio en noviembre de 1958, para ser reemplazado no por un guitarrista, sino por el baterista Ed Thigpen. Los años de 1957 a 1960 encontraron a Ellis de gira con Ella Fitzgerald.

A Ellis no le importaba trabajar a la sombra de los grandes. Hay que destacar sus rítmicos y brillantes solos en el trío de Peterson y en los discos y actuaciones con otros guitarras que siempre le sirvieron para dar lo mejor de sí mismo.

Los últimos años sesenta y primeros setenta, con el cambio de los gustos del jazz lo llevaron a trabajar como músico de sesión en Los Ángeles5​ y para los estudios televisivos. Después formó un supertrío de guitarristas The Great Guitars con Barney Kessel y Joe Pass, al que también se unieron en ocasiones Charlie Byrd y Tal Farlow.

Siguió grabando discos con regularidad bajo su propio nombre hasta los años noventa. Estuvo también trabajando en el espectáculo de Steve Allen, en el que se interpretaba a grandes compositores de jazz, tanto por parte del Kessel como de la orquesta del espectáculo, la Donn Trenner Orchestra, en la que trabajaban músicos como Ellis y el trombonista Frank Rosolino.

Ellis le dio lecciones de guitarra al dibujante y creador de The Far Side, Gary Larson, a cambio de la ilustración de portada del álbum Doggin 'Around (Concord, 1988) de Ellis y el bajista Red Mitchell.

En 1994 se unió al Arkansas Jazz Hall of Fame. El 15 de noviembre de 1997 recibió un Doctorado Honorario de la Universidad de North Texas College of Music.

Ellis murió de la enfermedad de Alzheimer en su casa de Los Ángeles la mañana del 28 de marzo de 2010, a la edad de 88 años.