达拉斯小牛队在1980-1981赛季加入NBA，很快就成为一支有竞争力的球队。在80年代，小牛队一直被看成是一支很有前途的球队。但在90年代初，小牛队开始下坡路，两度逼近球队最差战绩。从90年代中期开始，小牛队重新开始恢复元气。1999年小牛队选中诺维斯基后，正式成为西部劲旅，并于2005-06赛季进入总决赛。2010-2011赛季再次杀入总决赛，击败热队强势夺冠。
　　1994-1995赛季，小牛队选中的贾森-基德带来了新的希望。在新秀赛季中，基德平均每场就拿下11.7分5.4个篮板和7.7次助攻，他也与希尔成为当年的最佳新秀。加上贾马尔-马什本和吉姆-杰克逊，基德与他们组成名闻一时的“三J组合”。随着基德的加盟，小牛队本赛季的战绩有了惊人的提高，常规赛36胜46负，比上个赛季多赢了23场球，这是NBA历史上幅度最大的进步之一，最大幅度为从06-07到07-08的凯尔特人队，他们多胜了42场。 
　　“三J组合”没保持多久。1996-1997赛季，小牛队阵容大改组，“三J组合”分崩离析。96年12月，基德到了太阳队，小牛队得到芬利和AC-格林。97年2月7日，唐-尼尔森成为新总经理，他在一周内就将马什本送到热队，迎来了科特-托马斯，十天后他又将吉姆-杰克逊送到网队，得到了布拉德利等人。一个赛季下来，有27张面孔在小牛队出现，他们以24胜58负结束赛季。 
　　1999-00赛季，小牛队看到了复兴的曙光。常规赛40胜42负，距离进入季后赛仅一步之遥。仅仅进入NBA两年的诺维茨基表现日益出众，IT产业大亨马克-库班成为小牛队的新老板。 
　　2002-03赛季，小牛队形成了诺维茨基、芬利和纳什为核心的阵容，又迎来了拉弗朗茨和范埃克塞尔球队实力大增，小牛队以14连胜开局并继续扩大胜绩，将57胜变为60胜，在先后以两个4：3淘汰开拓者队和国王队后再次杀到西部决赛，但是仍以2：4的总比分惨遭当年的总冠军马刺的阻挡。 
　　2005-06赛季，小牛队常规赛60胜22负。在季后赛中，小牛队先是以4：0横扫灰熊队，再以4：3惊险淘汰马刺队，之后更是以4：2淘汰太阳队迈过西部决赛，闯入总决赛。不过第一次参加总决赛的小牛队在连赢两场的开局下，以2比4的比分输给了迈阿密热火队。 
　　2010-11赛季，小牛换走了老迈的丹皮尔，得到了钱德勒，大大增强了内线深度。但诺维茨基的伤病和巴特勒的赛季报销，使小牛遭到了沉重的打击。但随着诺维茨基的复出，佩贾斯托贾特维奇的加入，使小牛摆脱了困境。2月末小牛潜力后卫布博瓦复出，之后以57胜25负排名西部第三的战绩杀入季后赛。 
　　季后赛开打后，在诺维茨基、基德、马里昂、佩贾斯托贾特维奇等一帮老将的带领下，先后击败了开拓者队、湖人队，并凭着他们老道的经验及韧性以总比分4：1击败了年轻而富有活力的雷霆队，时隔5年后再次杀入总决赛。在总决赛中，小牛队多次上演逆转好戏，总比分4：2战胜迈阿密热火队，球队历史上第一次获得总冠军，德克诺维斯基获得总决赛MVP。