La idea la tuvo el empresario Don Carter en 1979, pero no fué hasta el año siguiente en el All-Star, cuando la aprovaron y se fundó el equipo, y debutaron en la temporada 1980-81.
En la temporada 1982-83 eran aspirantes a los play-offs por primera vez
En la siguiente en 1983 temporada eligieron en el draft Derek Harper, que jugó allí durante 10 años.
En la temporada 1983-1984, quedaron segundos en la división suroeste
En 1990 , el equipo tuvo que afrontar numerosos cambios.
En 1991 perdieron a una de sus estrellas Tarpley, sindo sancionado por malos actos.
En la temporada 1992 empezó la reconstrucción con varios traspasos importantes, y firmando su peor temporada con tan solo 11 victórias y 71 derrotas.
En 1993-1994 eligieron a Jamal Mashburn en el draft y ficharon como entrenador a Quinn Buckner, pero el inicio de temporada fue pésimo, con 1 victoria y 23 derrotas. Finalmente echaron al entrenador.
En la temporada del 1994-1995 adquirieron a Kidd y Tarpley volvió a jugar.También el tandem Jim-Jamal abandonaron el equipo. La mejora fue notable, ya que terminaron con 36-46, cerca de clasificarse a los play offs.
En la temporada 1995-1996 peridieron a 2 de sus estrellas y las otras 2 tuvieron conflictos internos, dando lugar a un 26-56.
Las 2 siguientes temporadas, 1996-1998, fueron una etapa de transición
1998-1999 fue una buena temporada registrando un decente 19-31, con un número de victórias en casa mayor que las derrotas, todo esto gracias a la adquisición de Dirk Nowitzki y de Steve Nash "Steve Nash
En la temporada 1999-2000 tuvieron una base de victorias bastante consolidadas, y el grupo Perot vendió la franquicia al empresario de Internet Mark Cuban por 285 millons de dolars
En la temporada 2000-2001 quedaron 53-29 con un consolidado triángulo ofensivo.
En la temporada 2001-2002 quedaron aún mejor que la anterior, con un 57-25
En la temporada 2002-2003 hubieron muchos fichajes nuevos y llegaron a play offs, pero decepcionaron cayendo en primera ronda.
En la temporada 2004-2005 llegaron nuevas incorporaciones y se fueron grandes jugadores, consiguiendo un balance de 58-24.
En la temporada 2005-2006 quedaron 60-22 y llegaron a la final por primera vez sn su historia
En la temporada 2006-2007 quedaron 67-15, ganando la liga
En la temporada 2007-2008 hicieron unos cuantos cambios en la plantilla y terminaron la temporada con
En la temporada 2010-2011 va ser cuando cnsiguieron el tan ansiado título, y fueron campeones
En las siguientes temporadas siguieron haciendo cambios constantemente pero sin llegar a ganar ningún título.
en el draft eligieronal joven Luca Doncic, quien lleva unos números uincreíbles hasta dia de hoy, siendo la principal estrella.