（1996-97赛季）小牛在1996-97赛季开始时阵中有著名的达拉斯三杰和乐观的新主教练。在赛季结束的时候，贾森-基德，贾马尔·马什本和吉姆·杰克逊都有了新的东家，这让吉姆-克里门斯用了创NBA纪录的27名队员。缺乏连续性让球队只取得了24-58的战绩，但是克里门斯给了任很大的希望，小牛终于有了成为一支成功球队的因素。
在12月小牛很令人吃惊的改变了球队未来的方向，将基德，托尼·杜马斯（TonyDumas）和洛伦·梅尔（LorenMeyer）换到太阳队，得到了AC·格林（A。C.Green），萨姆·卡塞尔（SamCassell）和迈克尔-芬利（MichaelFinley）。这个交易改善了球队的化学反应，也是球队开始大修的标志。
在2月7日，球队聘用了唐·尼尔森作为球队的总经理，全权接管球队的重建工作。尼尔森没有浪费一点时候。在一周内，他们与奥利弗·米勒（OliverMiller）和弗雷德·罗伯茨（FredRoberts）解约，将马什本送到热火队，得来了科特·托马斯（KurtThomas），萨沙·达尼洛维奇（SashaDanilovic）和马丁·穆尔塞普（MartinMuursepp）。
10天之后，小牛和新泽西篮网队完成了NBA历史上最大的交易之一，达拉斯送出了杰克逊，卡塞尔，埃里克·蒙特罗斯（EricMontross），乔治·麦克劳德和克里斯·加特灵（ChrisGatling，他在之前代表小牛参加了全明星赛）到纽约，得到了中锋肖恩·布拉德利，前锋埃德·奥巴农（EdO’Bannon）和后卫罗伯特·派克（RobertPack）和哈立德·里弗斯（KhalidReeves）。
当所有一切都完成之后，赛季初期的名单里只有德里克·哈珀和菜鸟萨马基·沃克（SamakiWalker）还留在了阵容当中。哈珀，这个非常受欢迎的小牛后卫以自有球员的身份续约，成为了NBA仅有的十位得分到达15000分，助攻得到6000个的球员之一。
小牛希望以NBA封盖最多的球员布拉德利（13.2分，8.4篮板，3.4封盖），芬利（15分），派克（14.3分，8.4助攻）和没有参加选秀但在菜鸟赛季能贡献10.3分的埃里克·斯特里克兰（ErickStrickland）作为核心进入1997-98赛季。
（1997-98赛季）很不幸，NBA的赛季取决于你赢得比赛的数量，而不是质量。在史书里，只会记下达拉斯小牛在1997-98赛季的战绩是20-62，但是小牛的铁杆们却在整个赛季都为那些最不可能取得的胜利而叫好。
小牛在11月1日主场的揭幕战中击败了超音速队，在最后5分01秒时间内打了对手一个23-2的*，最终以89-81获得胜利。在12月4日，当达拉斯小牛还在4-12的战绩面前挣扎时，总经理唐·尼尔森将主教练吉姆·克里门斯解约，自己亲自出马。尼尔森的开场就给了大家一个惊喜，他们轻松的以105-91战胜了10-6的尼克斯，芬利以27分拿到全场最高分。
就像令人意外的胜利一样，芬利表现出色的夜晚也在赛季中频频出现。在1月20日小牛以107-98再次击败超音速的比赛中，他得到了29分（埃里克-斯特里克兰得到了他职业生涯最高的30分）。一周之后，25-16的骑士队也在加时赛中以77-84死在小牛的刀下，那场比赛里，芬利得到职业生涯最高的39分和10个篮板。
前面所有的以弱胜强，包括之后战胜步行者、奇才和森林狼的比赛都只是这个主要时间的垫场而已。球队在加时赛里以104-97战胜了公牛队。他们在比赛还剩3：44的时候还以74-89落后，但是在最后的时间里，年轻的小牛送给卫冕冠军一个17-2的小*，将比赛拖进加时。
（1998-99赛季）对于达拉斯的球迷来说，1998-99赛季的每一个主场比赛，他们都可以看到全NBA最好的年轻球队之一的表演。
尽管小牛的战绩只有区区19-31，但是他们自1989-90赛季之后第一次在主场胜多负少，15-10。小牛队在4月取得了8-7的良好战绩，其中他们还击败了季后赛球队马刺、太阳、森林狼和火箭（两次）。
四年级后卫迈克尔·芬利已经逐渐成为升起的新星，他平均每场能攻下20.2分，也成为NBA仅有的在缩水赛季里总分达到1000分的10名球员之一。前锋加里·特伦特（GaryTrent）打的也不错，平均16分，7.8个篮板。
塞德里克·塞巴洛斯赛季的开局很出色，在13场比赛中平均得到12.5分。但是这个老兵前锋在2月25日对阵掘金的比赛中双腕骨折，缺席了之后的所有比赛。
（1999-00赛季）小牛队看到了复兴的曙光。常规赛40胜42负，距离进入季后赛仅一步之遥。仅仅进入NBA两年的诺维茨基表现日益出众，IT产业大亨马克·库班成为小牛队的新老板。
（2000-01赛季）小牛队终于扬眉吐气。常规赛53胜29负，11年之后重新进入季后赛。诺维茨基成为球队的中流砥柱。在季后赛第一轮，小牛队在0-2落后的局面下，连胜3场，淘汰了犹他爵士队，进入了第二轮。但来到第二轮，在马刺队面前，稚嫩的小牛队以1比4落败。
（2001-02赛季）小牛队搬到美国航线体育馆，球队战绩再上一层楼，取得创球队历史记录的57胜。由于在赛季中期，球队成绩西部第一，小牛队主教练老尼尔森还成为西部全明星队主教练。在季后赛，小牛队第一轮以3比0轻取森林狼队，但在第二轮他们以2比4败给国王队。
（2002-03赛季）小牛队形成了诺维茨基、芬利和纳什为核心的阵容，又迎来了拉弗朗茨和范埃克塞尔球队实力大增，小牛队以14连胜开局并继续扩大胜绩，将57胜变为60胜，在先后以两个4：3淘汰开拓者队和国王队后再次杀到西部决赛，但是仍以2：4的总比分惨遭当年的总冠军马刺的阻挡。
（2003-04赛季）小牛队获得52胜30负的战绩，但在季后赛首轮就被国王队以4：1淘汰。赛季结束后，纳什转会太阳队，老尼尔森离开小牛队，转往勇士队执教。
（2004-05赛季）小牛队斩获58胜24负，季后赛首轮以4：3淘汰拥有姚麦组合的火箭队，但在第二轮则以2：4不敌由昔日队友纳什领衔的太阳队。赛季结束后，芬利被特赦，转投马刺队。
（2005-06赛季）小牛队常规赛60胜22负。在季后赛中，小牛队先是以4：0横扫灰熊队，再以4：3惊险淘汰马刺队，之后更是以4：2淘汰太阳队迈过西部决赛，闯入总决赛。不过第一次参加总决赛的小牛队在连赢两场的开局下，以2比4的比分输给了迈阿密热火队。
（2006-07赛季）小牛在开局四连败的情况下打出67胜15负的联盟史上第六佳绩，并创造了球队历史最佳战绩。但季后赛第一轮被勇士以4：2淘汰，成就了对方的黑八奇迹。当家球星德克。诺维茨基获2006-07赛季常规赛MVP，他也是小牛队史上首位获次殊荣的球员。同时也是欧洲历史上第一位获此殊荣的球员。
（2007-08赛季）迫于湖人和太阳的大力扩军的压力，小牛老板库班几乎送出了半支球队（送出德文·哈里斯、迪奥普、莫莱斯·安格尔、特兰顿·哈塞尔和范霍恩，以及两个首轮选秀权和300万美元）换来了联盟中最好的组织后卫之一—贾森-基德，以在季后赛中走的更远。可惜的是在球员交换结束后小牛的成绩不如人意，最后只能排名西部第七，季后赛面对西部新贵黄蜂以1：4败下阵来，“小将军”约翰逊也因此被炒了鱿鱼。
（2008-09赛季）季后赛首轮遇马刺，经过5场恶战，最终以4比1淘汰马刺，晋级第二轮。第二轮遭遇拥有卡梅隆·安东尼和昌西·比卢普斯的掘金队，在缺少约什·霍华德的帮助下，小牛以1比4不敌掘金，无缘西部决赛。
（2009-10赛季）在交易大门关闭前夕（北京时间2月14日），小牛通过交易从奇才队得到了卡隆·巴特勒和布兰登·海伍德，最终排名西部第2，季后赛首轮再次遇到老冤家马刺，最终2：4败下阵来，成就了对方的“黑七奇迹”。
（2010-11赛季）小牛换走了老迈的丹皮尔，得到了钱德勒，大大增强了内线深度。但诺维茨基的伤病和巴特勒的赛季报销，使小牛遭到了沉重的打击。但随着诺维茨基的复出，佩贾斯托贾科维奇的加入，使小牛摆脱了困境。2月末小牛潜力后卫布博瓦复出，之后以57胜25负排名西部第三的战绩杀入季后赛。
季后赛开打后，在诺维茨基、基德、马里昂、佩贾斯托贾科维奇等一帮老将的带领下，先后击败了开拓者队、湖人队，并凭着他们老道的经验及韧性以总比分4：1击败了年轻而富有活力的雷霆队，时隔5年后再次杀入总决赛。在总决赛中，小牛队多次上演逆转好戏，总比分4：2战胜迈阿密热火队，球队历史上第一次获得总冠军，德克。诺维斯基获得总决赛MVP。
（2011-12赛季）小牛为腾出薪金空间在2012年夏天追逐自由市场“大鱼”，球队放走了钱德勒、巴里亚、史蒂文森和巴特勒，实力大减，卫冕冠军仅以西部第七晋级季后赛，在首轮即被雷霆队0：4横扫出局，成为NBA史上第8支季后赛遭横扫的卫冕冠军。
休赛期，小牛没能网罗到克里斯·保罗、德怀特·霍华德和德隆·威廉姆斯等一众大牌球星，只得靠小手笔交易得来卡曼、布兰德、OJ·梅奥和科里森一批不错的球员，但是这些球员还不足以拼起达拉斯的总冠军宏图。
（2012-13）这个赛季，尽管新援OJ·梅奥和克里斯·卡曼都有不错的表现，但是小牛队仍然步履瞒珊：诺维茨基缺阵29场，肖恩-马里昂缺阵15场；球员进进出出，一个赛季共有23人先后为小牛效力。同时，小牛的组织后卫达伦-科里森表现太差，他无法让小牛队运转起来。队中任何一个人来控球，几乎都能达到同样的效果。最终小牛在常规赛的战绩为41胜41负，这是球队自2000年起首次无缘季后赛。
2013年休赛期，小牛队试图得到克里斯·保罗和德怀特·霍华德中的一人但均告失败。取而代之地，小牛队通过签约找来维恩·艾灵顿、何塞·卡尔德隆、蒙塔·埃利斯、萨缪尔·戴勒姆波特、布兰登·莱特、德文·哈里斯、德胡安·布莱尔等一批新援。
球队老板：马克·库班，1964年3月26日出生在美国匹兹堡市，曾在印第安纳大学打过四年橄榄球，毕业后一直在俱乐部打球，1983年创立计算机资讯公司MicroSolutions，并在网络经济最繁荣的时候专卖给了美国最大的在线服务公司。2000年1月14日，库班购买了NBA球队达拉斯小牛队。马克·库班“为胜利不惜一切”的格言已经感染了整个球队，成为小牛队的精神。