（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赛季）对于达拉斯的球迷