（1996-97賽季）小牛在1996-97賽季開始時陣中有著名的達拉斯三傑和樂觀的新主教練。在賽季結束的時候，賈森-基德，賈馬爾·馬什本和吉姆·傑克遜都有了新的東家，這讓吉姆-克裡門斯用了創NBA紀錄的27名隊員。缺乏連續性讓球隊隻取得了24-58的戰績，但是克裡門斯給了任很大的希望，小牛終於有了成為一支成功球隊的因素。

  在12月小牛很令人吃驚的改變了球隊未來的方向，將基德，托尼·杜馬斯（TonyDumas）和洛倫·梅爾（LorenMeyer）換到太陽隊，得到了AC·格林（A.C.Green），薩姆·卡塞爾（SamCassell）和邁克爾-芬利（MichaelFinley）。這個交易改善了球隊的化學反應，也是球隊開始大修的標志。

  在2月7日，球隊聘用了唐·尼爾森作為球隊的總經理，全權接管球隊的重建工作。尼爾森沒有浪費一點時候。在一周內，他們與奧利弗·米勒（OliverMiller）和弗雷德·羅伯茨（FredRoberts）解約，將馬什本送到熱火隊，得來了科特·托馬斯（KurtThomas），薩沙·達尼洛維奇（SashaDaovic）和馬丁·穆爾塞普（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球隊達拉斯小牛隊。馬克·庫班“為勝利不惜一切”的格言已經感染了整個球隊，成為小牛隊的精神。