达拉斯小牛队在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。