1979-1992:新星的第一次興衰史
1979：卡特歡迎籃球來到達拉斯
在1979年，百萬富翁唐納德-J-卡特(DonaldJ.Carter)和小牛的首任主席和總經理諾姆-桑紐(NormSonju)著手準備擁有一支NBA球隊。在1980年的全明星賽期間，聯盟的主席們投票通過了德克薩斯擁有一支球隊。在繳納了1200萬的入門費之後，達拉斯獲得了在1980-81賽季進入NBA的許可。他們被分在了中西區進行。
在擴張選秀中，小牛放棄了有經驗的球星厄爾-門羅(EarlMonroe)，里克-巴里(RickBarry)，道格-科林斯(DougCollins)，皮特-馬拉威奇(Pete Maravich)和斯班瑟-海伍德(SpencerHaywood)等人，而相反的，他們選擇了18－22歲之間的年輕球員，他們最多的也就只有3年的NBA經驗。儘管這些球員都有一定的才華－他們當中的11個人都時曾經的第一輪新秀－但這是一個典型的擴張選秀陣容。他們當中最引人注目的名字是費城76人的吉姆-斯潘納科爾(JimSpanarkel)，克里夫蘭騎士的奧斯汀-卡爾(AustinCarr)，聖迭戈快船的羅伯特-“賓果”-史密斯(BingoSmith，本名羅伯特-史密斯，RobertSmith)和密爾沃基雄鹿隊的理察-華盛頓(RichardWashington)。
在1980年6月10日，小牛在NBA選秀中在第11順位選擇了UCLA的基基-范德維奇(KikiVandeweghe)，這也讓他成為了小牛球隊歷史上第一個大學選秀球員。但是范德維奇拒絕為這支新軍效力，他一直罷賽到常規賽開始一個月。最終在12月10日，達拉斯把他和1986年的第一輪選秀權交易給了掘金隊，換來了未來的兩個第一輪選秀權。
這個交易給小牛帶來了很大的好處。他們用其中的一個選秀權在1981年選來了羅蘭多-布萊克曼(RolandoBlackman)。之後布萊克曼成為球隊歷史上的得分王。另一個給球隊很大幫助的交易是，達拉斯將邁克-布拉茨(MikeBratz)交易到騎士換來了1984年的第一輪選秀權。達拉斯用這個選秀權選擇了薩姆-帕金斯(SamPerkins)，他在這個俱樂部的6個賽季里成為了相當可靠的大前鋒和中鋒。
羅蘭多-布萊克曼小牛最成功的動作是聘用了 迪克-莫塔(DickMotta)成為了球隊第一任主教練。他是一個出色的老師和籃球導師，他在1968－69賽季成為了公牛隊的教練，並且很快把這支球隊變成勝利者。在1970－71賽季公牛取得51－31之後，莫塔成為了NBA年度最佳教練。他在1975-76賽季之後離開公牛，來到了 華盛頓子彈隊，帶領他們在1978年取得NBA總冠軍。莫塔帶著541-443的戰績來到了達拉斯。
1980－81：緩慢的起步
小牛隊在耗資2700萬美元興建的團聚球館(ReunionArena)開始了他們的1980-81賽季。開場的主力包括阿卜杜爾-吉拉尼(AbdulJeelani)，傑羅姆-懷特海德(JeromeWhitehead)，湯姆-拉加德(TomLaGarde)，喬夫-赫斯頓(GeoffHuston)和溫福德-博因斯(WinfordBoynes)。達拉斯擊敗了馬刺隊，103－92，取得開門紅。吉拉尼得到球隊歷史上的前五分；博因斯取得了全隊最高的21分，拉加德也貢獻了19分和14次助攻。
賽季其他的比賽中都充斥著失敗的挫敗感，甚至是對一支新軍來說也是。在他們終於獲得第一次兩連勝之前，他們的開局是6-40，其中包括一次10連敗和一次12連敗。在11月8日，對陣底特律活塞的比賽中，莫塔加入了紅衣主教阿諾德-奧爾巴赫(RedAuerbach)，紅頭威廉-霍爾茲曼(RedHolzman)和吉恩-舒(GeneShue)的行列，執教了他的第1000場職業比賽。諷刺的是，莫塔因為被驅逐出場，缺席了第四節的比賽，小牛也以73-101慘敗。
達拉斯也有一些好運氣。在12月上旬，球隊簽下了自有球員，被活塞放棄的6尺3後衛布拉德-戴維斯(BradDavis)。他和小牛上下其他球員沒有什麼顯著的區別，他在大陸籃球聯盟(CBA)和NBA都有過打球的經歷。小牛隊觀察到他在CBA北安克雷奇騎士隊里的表現。對於戴維斯來說，到小牛效力和在安克雷奇沒有什麼顯著的區別，他計畫在這個賽季結束之後回到學校、
不過，戴維斯依舊在小牛打了56場常規賽比賽，在最後26場比賽中首發。他在3月3日和凱爾特人的比賽中平了吉拉尼當年取得的單場最高的31分。而且他的5.6次助攻也排名全隊第一，並且還有56.1%的投籃命中率。他的職業生涯獲得了新生，在之後的12年裡，他一直是小牛隊中重要的一員。
達拉斯以15-67的戰績結束了賽季。小牛平均每場得到101.5分，這是他們十年中的最低分。吉姆-斯潘納科爾以平均14.4分成為球隊的得分王，他88.7％的罰球命中率也排名聯盟第四。湯姆-拉加德以8.1個籃板成為小牛的籃板王。
1981-82：出色的選秀點燃了小牛的希望
眾多的交易讓小牛在未來的五年里獲得了9個第一輪選秀權，這讓他們得到了像薩姆-帕金斯，德里克-哈珀(DerekHarper)，羅伊-塔普利(RoyTarpley)和德特雷夫-施拉姆夫(DetlefSchrempf)這樣的一流球員。但是最直接的轉變來自1981年，達拉斯選擇的三名球員幫助這支魚腩成為了一支有一定競爭力的球員，他們分別是馬克-阿吉雷(MarkAguirre，第一順位)，羅蘭多-布萊克曼(第九順位)和傑伊-文森特(JayVincent，第24順位)。
在1981-82賽季，小牛隊進步了13場，取得了28-54的戰績，擺脫了中西區墊底的厄運，他們超過了爵士隊。小牛在開場賽中，將去年客場藍色的球衣換成了綠色。阿吉雷在他的第一場常規賽中得到了19分。在11月14日，他得到了42分，但是小牛依舊輸掉了比賽(七連敗)輸給了勇士隊。達拉斯的連敗達到了賽季最長的12場。考慮到他們開局的戰績是1-13，剩下賽季中他們的比賽就更顯得進步顯著了。
阿吉雷，這個6尺6的前鋒在每次得球後都會成為對手的威脅，他也成為了球隊逐漸進步的關鍵原因之一。他在達拉斯的7個多賽季中平均得到24.6分。菜鳥球員布萊克曼，一個6尺6有著甜蜜手感的後衛，同樣也在小牛度過了一個長而多產的職業生涯。在他為球隊效力的11個賽季中，平均貢獻19.2分，同時也是一名可靠的防守者。
在12月15日，文森特，一個6尺7的前鋒頂上了阿吉雷受傷之後的空缺，並且用一場31分和13個籃板的表現帶領球隊擊敗了華盛頓子彈隊。這也是他本季15場30＋表現的開始。他在12月29日對陣堪薩斯城國王的比賽中得到了職業生涯最高的41分。
達拉斯在一月迎來了他們的第一個四連勝，這對於一支年輕球隊是一個相當大的鼓舞。文森特繼續著自己手熱的發揮，而替補後衛阿蘭-布里斯托(AllanBristow，他之後成為了一名NBA教練)也提供了全面的支持。在一月末的時候，小牛已經從開局1-13的陰影中走了出來，在這之後他們的戰績是12-15。儘管他們不能一個賽季都如此堅持，但是他們給了大家一定的希望。在這一年裡，文森特以21.4分領跑全隊，並且入選了NBA最佳新秀第一隊。阿吉雷也有18.7分的貢獻。
1982-83：一支有競爭力的球隊
在1982-83賽季，小牛隊證明了他們是一支在不斷進步的球隊。他們這個賽季的戰績是38-44，比去年又提高了10場，也是NBA進步第三大的球隊。更多的，聯盟已經開始不再將小牛當作是一支擴張選秀的新軍了，而開始將他視作是一個危險的對手。
在1月14日，僅僅在對華盛頓得比賽中只得了84分之後，小牛打破了隊史得單場得分紀錄，他們以149-139擊敗了丹佛。羅蘭多-布萊克曼的31分是球隊最高，而馬克-阿吉雷也得到了球隊歷史上第一個三雙：30分11個籃板16次助攻。達拉斯在1月18日擊敗了金州勇士隊，讓莫塔成為了NBA第五位取得600勝的教頭。四天之後，他們以126-88狂勝尤他，38分的分差也是球隊歷史上最大的勝利。又過了4天，小牛戰勝了堪薩斯國王，取得五連勝。
小牛隊的華麗表演還在繼續，阿吉雷在2月6日在擊敗開拓者的比賽中得到44分。小牛隊在全明星休假之前的15場比賽中取得了12場勝利，他們也以25-24的戰績爬升到中西部賽區的第二名。
球隊在賽季的後半段跌回凡間。他們在賽季結束前兩周的那個7連敗讓他們徹底失去了爭奪季後賽席位的資格。在告別季後賽之後，他們在最後一場的常規賽里慘遭蹂躪，眼睜睜的看著馬刺在132-120戰勝他們的比賽中取得了破球隊歷史紀錄的70.7%的命中率。
儘管結局很讓人失望，當時1982-83賽季的小牛在整個賽季里都給人感到很有希望。小牛在全隊得分方面以場均112.7分排名聯盟第五，並且場均16.4次的失誤也比其他所有球隊都來得要少。馬克-阿吉雷以24.4的平均得分成為球隊的得分王，在全聯盟他的這一成績也排名第六；在他身後的是18.7分的傑伊-文森特和17.7分的羅蘭多-布萊克曼。布拉德-戴維斯在三項技術統計中就名列聯盟前十：57.2%的投籃命中率排名第八(後衛中的第一)，7.2次助攻名列第十，84.5%的罰球命中率排名第六。
球隊在1983年選秀大會上選擇了6尺4寸，來自伊利諾伊大學的後衛德里克-哈珀，這繼續加強了球隊的實力。哈珀在未來的10年裡也有平均15分和6.1次助攻的成績送出。
1983-85：小牛第一次晉級季後賽
在1983-84賽季，小牛隊經歷了他們的第一個勝多負少的賽季，他們以43-39的戰績在猶他爵士之後排名中西部賽區第二。同樣是在他們的第四個賽季中，他們也第一次出現在了季後賽球隊的名單之中。
小牛的開局相當順利，他們的戰績是10-3(是球隊歷史最好的第一個月戰績)，其中還包括主場的九連勝。在11月17日，小牛隊開始了他們當時隊史最長的八連勝。阿吉雷在背靠背對勇士和聖迭戈快船隊的比賽中連續得到40分。他同時也成為了隊史上第一位入選全明星陣容的球員。
小牛繼續以他們的火力給對手帶來威脅。在3月24日對丹佛的比賽中，阿吉雷在第四節單節得到24分，全場得到46分；同時布萊克曼也貢獻了38分。在4月上旬，一般上場時間不多的後衛戴爾-埃利斯(DaleEllis)在7場比賽中以連續8個三分球創造了NBA的紀錄(後來被湖人的科比-布萊恩特(KobeBryant)在對超音速的比賽中打破)。
在這個賽季中，阿吉雷平均每場得到29.5分，在NBA名列第二，僅僅落後於場均30.6分的阿德里安-丹特利(AdrianDantley)。布萊克曼以22.4分名列第13，而布拉德-戴維斯在助攻榜上排名第十，每場能送出6.9次助攻。連續的第二個賽季，小牛隊又在失誤榜上排名第一，他們的15.9次失誤比其他隊伍都要少。
儘管小牛在1983-84賽季的最後一場常規賽中輸給了勇士，但是他們已經取得了西部第四的好成績。在球隊的第一次季後賽經驗中，小牛隊在第一輪五局三勝的比賽中3-2擊敗了超音速隊。其中第五場比賽他們是通過加時賽以105-104戰勝對手。在西部半決賽里，他們輸給了洛杉磯湖人隊，最終打進決賽的湖人以4-1擊敗了他們。
多虧了1980年的那次交易，小牛在1984年得到了騎士的第一輪選秀權。由於騎士在前一賽季只取得了28-54的糟糕戰績，小牛得到了第四順位。他們選擇了北卡羅萊納大學6尺9的大個子薩姆-帕金斯，在之前的一個順位中，公牛隊選擇了同樣來自北卡的麥可-喬丹(MichaelJordan)。帕金斯幫助北卡獲得了1982年NCAA的冠軍，並且把他高效的、多變的比賽風格帶到了NBA，他在小牛的6個賽季中平均得到14.4分和8個籃板。之後他來到了魔術師領軍的湖人，那時已經是那個王朝的最後時期了。在九十年代，他又到西雅圖為超音速隊效力。
1984-85賽季的小牛比上個賽季的成績提高了一場，44-38，連續第二年獲得西部第四。帕金斯入選了最佳新秀陣容，而馬克-阿吉雷再一次成為球隊的得分王，場均貢獻25.7分。在1月28日，阿吉雷用對76人得到的49分打破了他曾經保持的單場得分紀錄。羅蘭多-布萊克曼代表球隊參加了1985年的全明星賽。而莫塔在3月10日在126－113擊敗籃網的比賽之後成為了NBA第四位取得700勝的教練。
馬克-阿吉雷達拉斯有才華橫溢的球員，但是他們能成功的最主要原因是他們一年都保持健康。小牛連續第三年成為NBA失誤最少的球隊，只有14.4次。他們152個三分命中也是NBA最多的，這成了球隊另一個特點。
小牛隊連續第二年打進了季後賽，但是在第一輪被波特蘭開拓者淘汰。小牛在五局三勝的對局中的第一場通過兩個加時險勝對手，但是之後三場開拓者取得三連勝。
1985-86：選擇德特雷夫，交易到唐納德森
在1985-86賽季小牛取得了另外一個44-38的戰績，繼續保持著競爭者的角色。俱樂部通過在1985年選秀大會上選擇的德特雷夫-施拉姆夫繼續增加球隊的才華。這一次，這個選秀權同樣也是來自之前和騎士隊的交易。德國人施拉姆夫是一個全面的6尺10的前鋒，他之前在華盛頓大學打球。另外，在使用過6個馬馬虎虎的中鋒之後，小牛隊在11月25日從快船隊交易得到了7尺2的中鋒詹姆斯-唐納德森(JamesDonaldson)，他們付出的球員是科特-尼姆菲尤斯(KurtNimphius)。
達拉斯舉辦了1986年的NBA全明星賽，而羅蘭多-布萊克曼連續第二次在賽季中期代表小牛出戰。布萊克曼在3月12日對陣薩克拉門托國王隊的比賽中獨得46分，是馬克-阿吉雷前一年得到49分之後的球隊歷史第二高分。
小牛隊成為了進攻火力很強的球隊，場均能得到115.3分，排名聯盟第二，僅次於強大的洛杉磯湖人隊。個人得分方面比去年還要平均：阿吉雷(22.6分)和布萊克曼(21.5分)領跑全隊，而薩姆-帕金斯，傑伊-文森特和德里克-哈珀也都有兩位數的得分。唐納德森在籃板方面排名聯盟第九，場均9.6個籃板。球隊連續第四年場均失誤最少，並且連續第二個賽季命中最多的三分。
達拉斯在1986年NBA季後賽里第一輪擊敗了猶他爵士隊，之後輸給了最終的冠軍洛杉磯湖人隊。湖人以4-2取勝，其中四場比賽的分差小於或等於4分。
小牛在1986年NBA選秀中選擇了大個子羅伊-塔普利。這個來自密西根大學的7尺前鋒最終被認為是小牛很好的球員之一-也是最悲傷的故事。
1986-87：球隊取得50勝，在季後賽中崩潰
在1986-87賽季中，小牛隊已經被當成是NBA很有實力的球隊了，隊中眾多多才的年輕人預示著一段美好的未來。小牛取得了55-27的常規賽戰績，最終成為中西部賽區冠軍。
球季的揭幕戰里，小牛便將對手爵士隊的命中率壓制在31.1％，體現了在防守方面的努力的決心。一周之後，小牛擊潰了超音速，147-124，9名球隊同時取得雙位數的得分也創造了NBA的紀錄，在11月26日，一向小心謹慎的小牛在對國王的比賽中平了他們之前創造的單場4次的失誤紀錄。主場13-1的戰績也創下球隊紀錄。
小牛的主力陣容變成了馬克-阿吉雷，薩姆-帕金斯，詹姆斯-唐納德森，德里克-哈珀和羅蘭多-布萊克曼。德特雷夫-施拉姆夫，羅伊-塔普利和布拉德-戴維斯組成主要的替補。每個位置，球隊都充滿才華，而且球員都很全面，這給NBA所有的對手都造成了麻煩。在一月，施拉姆夫取得了球隊第三個三雙。在三月，唐納德森用704個籃板打破了傑伊-文森特在1984-85賽季創造的總籃板紀錄。當年三月球隊取得了球隊歷史最好的戰績12-4，包括莫塔在3月28日對華盛頓時取得的第800勝。
就像以往一樣，小牛再一次成為全聯盟失誤最少的球隊，場均只有14.7次。而即使聯盟的其他球隊都已經把三分球當作是一項常規的進攻手段，而不只是暗器或者救命稻草，小牛依舊投中了聯盟最多的231個三分球，他們場均能得到116.7分。唐納德森打破了球隊的籃板球紀錄，並且以場均11.9個三分成為中鋒中的籃板王。
在常規賽中從沒有三連敗的小牛隊，在季後賽里崩潰了。在季後賽的揭幕戰中，小牛在151-129戰勝超音速的比賽里創造了球隊季後賽里的11項紀錄。但是之後，他們連折三陣。超音速隊中最大的功臣是原小牛的球員戴爾-埃利斯，他在西雅圖得到重生，並且成為了NBA最優秀的三分手之一。
在1986-87賽季之後，迪克-莫塔意外的辭去了主教練的之後，然後球隊任命了約翰-麥克洛德(JohnMacLeod)。麥克洛德之前在菲尼克斯太陽隊執教長達14年，總戰績是579-543。他9次將太陽帶進季後賽，並且在1976年帶領球隊獲得總冠軍。
1987-88：只差一場就能進軍總決賽
1987-88賽季的小牛延續了前一個賽季的強勢，取得了53-29的戰績。麥克洛德也在1月13日球隊戰勝步行者的比賽中取得了職業生涯第600勝，那場比賽里羅伊-塔普利抓下了23個籃板。馬克-阿吉雷和詹姆斯-唐納德森參加了1988年的全明星賽。之後，從2月14日開始，球隊開始了歷史最長的11連勝。在2月24日，在球隊連續第六場的勝利中，布萊克曼得到了他職業生涯的第10000分。
在4月15日的失利之後，小牛從12月21日以來第一次丟掉了中西部賽區第一的位置。在110天排名第一之後，他們被丹佛掘金之後，最終一一場之差排名賽區第二。
阿吉雷連續第六個賽季成為了球隊的得分王，場均25.1分。塔普利以場均13.5分和11.8個籃板的成績榮膺NBA最佳第六人。
在1988年，小牛隊經歷了最好的季後賽之旅。在分別經過4場和6場激戰淘汰火箭和掘金之後，小牛球隊歷史上第一次進入西部決賽。阻擋在球隊和NBA總決賽之間的是衛冕冠軍洛杉磯湖人隊。小牛盡了自己最大的努力，但是湖人的季後賽經驗起到了冠軍的作用。湖人在第七場決勝戰中以117比102戰勝了小牛。
1988-90：小牛無緣季後賽；重組
傷病折磨了1988-89賽季的小牛隊，他們發現戰績滑落到了38-44。小牛在1982-83賽季之後第一次勝少負多並且無緣季後賽。小牛隊在麻煩到來之前取得了9-3的開局。在1月開始的時候，球隊突然變得不能控制了。羅伊-塔普利因為聯盟藥檢的政策從1月5日開始被無限期禁賽。一周之後，迷茫的小牛輸掉了連續六場比賽。
在二月中選，小牛將馬克-阿吉雷送到即將成為總冠軍的活塞隊，換來了阿德里安-丹特利。他們倆都是以喜怒無常聞名的球星。當丹特利知道他要被交易的時候，他拒絕到達拉斯報到，不過八天之後，他還是來到了球隊。而當丹特利還在罷賽的時候，小牛又將德特雷夫-施拉姆夫送到步行者，換來了赫伯-威廉士(HerbWilliams）。全能的施拉姆夫最終在1993年加盟超音速之前在步行者獲得了兩個最佳第六人獎盃。
在3月10日，詹姆斯-唐納德森因為膝蓋肌腱撕裂倒下了，他被擔架抬離賽場，缺席了球隊之後的比賽。傷痕累累的小牛失去了那么多的關鍵球員，這也嚴重影響了球隊的士氣。剩下的賽季對於他們來說只是熬時間而已。
小牛在1989-90賽季出現了反彈，他們取得了47-35的戰績。小牛仍然是一支可靠的、有才華的、防守至上的球隊，球隊中包括阿德里安-丹特利，赫伯-威廉士，羅伊-塔普利，薩姆-帕金斯，羅蘭多-布萊克曼和德里克-哈珀。
但是，這也是一個不安靜的賽季。在11月15日，賽季開始僅僅6場比賽之後，塔普利因為酒後駕駛和反抗拘捕被逮捕。在11場比賽取得5-6的戰績之後，主教練約翰-麥克洛德被助理教練里奇-阿杜巴托(RichieAdubato)取代。球隊在賽季中期還依然在掙扎，但是他們在之後分別取得了七、五和六連勝。哈珀在12月29日對開拓者的比賽中取得了職業生涯最高的42分。小牛隊隊史的籃板王，在同一場比賽中抓下了27個籃板。
球隊在賽季的後期狀態相當出色。在4月4日，小牛平了隊史上最大的翻盤，在落後馬刺19分的情況下翻盤成功。薩姆-帕金斯在4月12日擊敗勇士的比賽中得到職業生涯最高的45分。小牛以四連勝結束了賽季，之後被開拓者在第一輪中被淘汰。開拓者在進入總決賽的路上將小牛橫掃出局。
1990-91：從強隊行列中墮落
在出色的1989-90賽季之後，新賽季似乎成了88-89年的翻版。小牛貌似走在正確的軌道了，但是事實上，這條路卻把球隊帶往懸崖邊上。很多NBA球隊都經歷著這樣的輪迴：成功，衰敗，重建。但是小牛的情況卻不一樣，他們更像是直接的自由落體，而很少有NBA球隊會這樣。在接下來的兩個賽季中，他們成為聯盟里最爛的球隊之一，他們甚至不是那些後來的NBA新軍的對手，而且還總不斷挑戰著NBA的一些最差紀錄。
小牛的陣容繼續變化著。1990年薩姆-帕金斯以自由人的身份來到湖人，而羅德尼-麥克雷(RodneyMcCray)，“胖子”列弗(FatLever)和阿列克斯-英格利什(AlexEnglish)都在職業生涯的末期出現在小牛陣營當中。事實上，1990-91賽季，陣容中所有的球員都經歷了大大小小的傷病，這導致他們最終的戰績只有28-54，這個戰績比兩支新軍奧蘭多魔術和明尼蘇達森林狼都要差。
球隊的問題很早就出現了。在11月6日，羅伊-塔普利用29分10個籃板的成績帶領小牛戰勝了尼克斯。然後三天之後，球隊就宣布“胖子”列弗將進行右膝手術，並將缺席本賽季剩餘的所有比賽。在那天晚上的比賽中塔普利的膝蓋骨也嚴重受傷，他也缺席了賽季之後的所有比賽。在這兩人缺席之後，球隊開始了嚴重的下滑。
在11月28日，布萊克曼超過了馬克-阿吉雷成為球隊歷史上得分最多的球員，這個裡程碑在混亂的賽季中幾乎被遺忘。在3月，塔普利的職業生涯又出現困難。他因酒後駕車被起訴，並再次被NBA停賽。
1991-92：開始重建
1991-92賽季，掙扎中的小牛戰績滑落到了22-60。在10月16日，塔普利因為濫用藥物被NBA第三次禁賽。這對於一個曾經有過輝煌的球員來說是一個很大的打擊。塔普利在1986-87賽季入選了NBA最佳新秀陣容，並且在那個賽季後期嘗試過戒毒。在1987-88賽季，他當選最佳第六人。在1988-89賽季中期，他被聯盟停賽49場。在1990-91賽季，他因為膝蓋的傷勢缺席了77場比賽。他在89-92年間因為傷病和停賽只參加了246場比賽中的69場。在這期間，有他參加的比賽小牛的戰績是45-24(.652)，沒有他參加的時候只有68-109(.384)。
球隊就只剩下4、5個好球員了，而這些才華也被不斷的傷病沖走。 布拉德-戴維斯在一月中旬背部受傷，宣布退役。“胖子”列弗在1月29日進行了膝蓋手術，並且缺席了剩餘的比賽。在他效力 丹佛掘金隊的全盛時期，他是NBA後衛中最全能的隊員。但是這個讓小牛付出了未來兩個首輪選秀權的球員卻因為膝傷只為小牛出場了35場比賽。
這個賽季小牛創下的所有球隊紀錄都不是他們想創造的。在三月他們經歷了15連敗；客場26連敗；隊史最低也是當季聯盟最差的場均97.6分；隊史最低的43.9％全隊命中率。小牛在那個賽季有19次得分沒有上90。看到這樣的情況，球隊開始清理隊中的老球員，並且開始重建。
在1992-93賽季之前，小牛將 羅蘭多-布萊克曼送到紐約，換來了未來的第一輪選秀權。布萊克曼離開小牛的時候是球隊歷史上最受歡迎的球員，並且也是隊史得分王。在他為小牛效力的11個賽季中，他一共得到了16643分，四次被選為全明星。
赫伯-威廉士以自有人的身份也去了尼克斯，而“胖子”列弗又進行了更多的手術，並且缺席了整個1992-93賽季。球隊僅剩的經歷過球隊光輝時期的球員是10年的老兵德里克-哈珀，他在1992-93賽季以18.2的場均得分名列球隊第一。
1992-1997:達拉斯3J時代的短暫輝煌
1992-93：小牛避免了尷尬的紀錄
小牛把希望都寄予在年輕人的身上，不過那其中並不包括在第四順位選擇的新人吉姆-傑克遜(JimJackson)。他和球隊老闆在契約問題上出現很大的分歧，這導致了他在長達半個賽季的時間裡被排在球隊大名單之外。
由於老球員都離開了，年輕人還沒有及時的頂上來，小牛在1992-93賽季根本沒有在NBA競爭的實力。在被剛入聯盟的幾個選秀權用盡了好運氣之後，小牛在這次下滑期的高位選秀中就沒有了那么幸運了。道格-史密斯(DougSmith)和蘭迪-懷特(RandyWhite)，他們都能勉強立足於NBA，但是並沒有像預期的那樣成為超級巨星。
在陣容被交易，傷病和契約問題削弱了很多之後，小牛在1992-93賽季一蹶不振。那是一愕鬲噩夢般的賽季，他們分別經歷了12，15和19連敗。在1月13日，當小牛僅僅取得2勝27負的戰績之後，主教練里奇-阿杜巴托被解職，助理教練加爾-赫德(GarHeard)上任。在六天之後，赫德取得了他的第一場勝利，中止了漫長的15連敗。
隨著賽季的進行，重建中的小牛離創造NBA歷史的最差戰績越來越近。之前最差的戰績是76人在1972-73賽季創造的9-73。而在61場比賽結束後，小牛的戰績只有4-57。
但是，在3月3日最終與吉姆-傑克遜簽約和奎因-巴克納(QuinnBuckner)正式接任球隊主教練之後，球隊的士氣得到了很大的提升，最終避免了創造尷尬的紀錄。傑克遜出現在了小牛最後的28場比賽中，平均貢獻16.3分。在最終的21場比賽中幫助球隊取得了7-14的戰績，其中包括一次兩連勝，球隊最終的戰績定格為11-71。
1993-94：選擇了奎因，但是依舊得不到勝利
球隊在1993-94賽季留任了奎因-巴克納。他是一個聰明的人，總是為勝利者打球，在大學時他在印第安納大學，而來到NBA他又先後效力雄鹿，凱爾特人和步行者隊。儘管他的數據在NBA只是一般，但他效力球隊的戰績卻有61.9%。人們希望他贏球的趨勢能在這支球隊得到延續。
在1993年NBA選秀中，小牛隊在第六順位選擇了肯塔基大學的賈馬爾-馬什本(JamalMashburn)。這個全能的6尺8前鋒被希望能夠給前場的得分帶來幫助，並且組成球隊的新核心。不過小牛依然面對著漫長而困難重重的重建之路。
在1993-94賽季，NBA的競爭對於小牛來說依然太過激烈。在傑克遜和馬什本的帶領下，球隊的確有了更好的狀態，也的確有了小小的進步。但是巴克納嚴厲的執教風格在一開始並沒有起到良好的效果，小牛的開局只有1-23，在一月結束的時候也只有3-40。
由於害怕創造NBA最差戰績的陰影再次襲來，小牛上下開始感覺到很強的壓力。巴克納讓球隊放鬆下來，球隊也以一些能量充沛的表現回報了他。小牛在2月和4月的戰績都是5-18，最終取得13-69的戰績。他們必須感謝森林狼讓他們避開了尷尬，小牛在對陣森林狼時取得了他們全部13場勝利中的5場。
儘管賽季非常艱苦，但是小牛的兩桿小槍卻顯示了美好的未來。馬什本的場均19.2分是新秀中最高的，而傑克遜更是顯出了有三雙的潛力，取得了全隊最高的4.6次助攻，得分追平馬什本，而籃板也是全隊第二的4.7個。
在賽季結束的時候，達拉斯解僱了巴克納，並重新請回了迪克-莫塔，球隊歷史上的第一任，並且打造了80年代球隊輝煌的教練。小牛同時也得到了另一位才華橫溢的球員，他們在1994年選秀大會上選擇了加利福尼亞大學的後衛傑森-基德(JasonKidd)。
1994-95：基德讓小牛時來運轉
小牛在1994-95賽季取得了顯著的變化。在前一賽季的戰績只有13-69之後，他們的戰績在這一年進步了23場，變成36-46，是NBA歷史上進步最大的進步幅度。36場勝利比小牛在前兩個賽季取得的獲勝場次相加還多。
球隊進步最主要的催化劑是新秀控衛傑森-基德，他的4次三雙是NBA最多的，並且場均得到11.7分，5.4個籃板和7.7次助攻。在他的努力下，基德和活塞隊的格蘭特-希爾(GrantHill)共同獲得了年度最佳新秀。基德的助攻數排在聯盟第十，而搶斷數更是排在第七。小牛在4月11日經過兩個加時以156-147戰勝了火箭隊，基德取得了三雙(包括38分)，而他在第一個加時的最後55秒時間內投中了3個三分。
基德給了小牛新的希望基德和另外兩年才華橫溢的年輕人賈馬爾-馬什本以及吉姆-傑克遜成為了全聯盟攻擊火力最強的三人組。後兩者也都是他們個子位置上數一數二的好手，馬什本以場均24.1分排名聯盟第五。而儘管傑克遜在二月扭傷了腳踝，並缺席了賽季剩餘的比賽，他依然場均貢獻25.7分，但是很遺憾他沒有資格被列入最終的得分榜。
二年級前鋒 波派-瓊斯(PopeyeJones)同樣也有一個很好的賽季。他平均得到的10.6個籃板讓他進入聯盟前十。瓊斯抓下的329個前場籃板十NBA球員中最高的。羅伊-塔普利，這個之前被NBA禁賽的球員在94-95賽季之前被解禁。他重新回到球隊陣中，並且場均貢獻12.6分和8.8個籃板。
1995-96：卡特， 莫塔時代在失望中結束
在經歷了一個不錯的94-95賽季之後，小牛在95-96賽季職取得了令人失望的26勝。迪克-莫塔第二次執教小牛的經歷就此結束，而球隊也第一次更換了所有權。
在那個賽季之前，一些球員開始談論他們將更進一步，進入季後賽。4-0的開局也貌似和他們的承諾相一致。但是傷病，內線實力匱乏，缺少有經驗的老將和內在的衝突改變了球隊的命運。
在僅僅18場比賽之後，馬什本就因為要進行左膝手術結束了整個賽季。傑克遜和基德在有些時候不能很好的配合，但是他們倆各自分別有明星級的表現都不是問題。基德成為小牛第一位全明星首發，他最終在助攻榜上排名第二(9.7次)，搶斷榜排名第四(2.2次)。傑克遜成為球隊的得分王，並且是僅有的一位打滿全部82場比賽的球員。
由於沒有內線的支持，小牛的進攻更多的倚賴於三分投射，他們的三分命中數(735)和試投數(2039)都是NBA第一。喬治-麥克勞德(GeorgeMcCloud)在馬什本受傷時候重現浮出水面，他場均得到18.9分，並且投中了257個三分，是聯盟歷史上第二多。
在賽季結束的時候，迪克-莫塔的位置被來自公牛的助理教練吉姆-克里門斯(JimCleamons)取代。而球隊的所有權也被唐納德-卡特出售，購買者是以前總統競選人之子小羅斯-佩羅特(RossPerotJr).為首的投資團。
1996-97：小牛修補，重建
96-97賽季，達拉斯3J解體小牛在1996-97賽季開始時陣中有著名的達拉斯三傑和樂觀的新主教練。在賽季結束的時候，傑森-基德，賈馬爾-馬什本和吉姆-傑克遜都有了新的東家，這讓吉姆-克里門斯用了創NBA紀錄的27名隊員。缺乏連續性讓球隊只取得了24-58的戰績，但是克里門斯給了任很大的希望，小牛終於有了成為一支成功球隊的因素。
在12月小牛很令人吃驚的改變了球隊未來的方向，將基德，托尼-杜馬斯(TonyDumas)和洛倫-梅爾(LorenMeyer)換到太陽隊，得到了AC-格林(A.C.Green)，薩姆-卡塞爾(SamCassell)和麥可-芬利(MichaelFinley)。這個交易改善了球隊的化學反應，也是球隊開始大修的標誌。
在2月7日，球隊聘用了唐-尼爾森(DonNelson)作為球隊的總經理，全權接管球隊的重建工作。尼爾森沒有浪費一點時候。在一周內，他們與奧利弗-米勒(OliverMiller)和弗雷德-羅伯茨(FredRoberts)解約，將馬什本送到熱火隊，得來了科特-托馬斯(KurtThomas)，薩沙-達尼洛維奇(SashaDanilovic)和馬丁-穆爾塞普(MartinMuursepp)。
10天之後，小牛和新澤西籃網隊完成了NBA歷史上最大的交易之一，達拉斯送出了傑克遜，卡塞爾，埃里克-蒙特羅斯(EricMontross)，喬治-麥克勞德和克里斯-加特靈(ChrisGatling，他在之前代表小牛參加了全明星賽)到紐約，得到了中鋒肖恩-布拉德利(ShawnBradley)，前鋒埃德-奧巴農(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-2005:老尼爾森賦予了球隊新的歷史
1997-98：勝利很振奮人心，但場次並不夠
很不幸，NBA的賽季取決於你贏得比賽的數量，而不是質量。在史書里，只會記下達拉斯小牛在1997-98賽季的戰績是20-62，但是小牛的鐵桿們卻在整個賽季都為那些最不可能取得的勝利而叫好。
小牛在11月1日主場的揭幕戰中擊敗了超音速隊，在最後5分01秒時間內打了對手一個23-2的高潮，最終以89-81獲得勝利。在12月4日，當達拉斯小牛還在4-12的戰績面前掙扎時，總經理唐-尼爾森將主教練吉姆-克里門斯解約，自己親自出馬。尼爾森的開場就給了大家一個驚喜，他們輕鬆的以105-91戰勝了10-6的尼克斯，芬利以27分拿到全場最高分。
在球隊得分(場均21.5)、助攻(場均4.9)和搶斷(場均1.61)上都位列首位的芬利是球隊中唯一打滿整個賽季的球員。在這個賽季中，球隊經歷了教練的更迭，而傷病的困擾則讓羅伯特-派克和科特-托馬斯在大部分賽季里都只能作壁上觀。肖恩-布拉德利，薩馬基-沃克，塞德里克-塞巴洛斯(CedricCeballos)和克里斯-安斯蒂(ChrisAnstey)也都長期受傷病困擾。
就像令人意外的勝利一樣，芬利表現出色的夜晚也在賽季中頻頻出現。在1月20日小牛以107-98再次擊敗超音速的比賽中，他得到了29分(埃里克-斯特里克蘭得到了他職業生涯最高的30分)。一周之後，25-16的騎士隊也在加時賽中以77-84死在小牛的刀下，那場比賽里，芬利得到職業生涯最高的39分和10個籃板。
前面所有的以弱勝強，包括之後戰勝步行者、奇才和森林狼的比賽都只是這個主要時間的墊場而已。球隊在加時賽里以104-97戰勝了公牛隊。他們在比賽還剩3:44的時候還以74-89落後，但是在最後的時間裡，年輕的小牛送給衛冕冠軍一個17-2的小高潮，將比賽拖進加時。
最值得紀念的個人成就要數11月20日，前鋒AC-格林連續出場907場比賽的時候，這也創造了NBA的一項新紀錄。格林，從1986年11月18日以來就再沒有缺席過一場NBA的比賽，在這個賽季結束時將這項紀錄延續到了978場。
1998-99：主場，甜蜜的主場
老尼爾森培養的諾維斯基和納什後來都奪得過常規賽MVP對於達拉斯的球迷來說，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日對陣掘金的比賽中雙腕骨折，缺席了之後的所有比賽。
1990-2000：小牛強勢收尾
離上一次小牛能連續品嘗到勝利的滋味已經有些時日了。1999-2000的小牛也並沒有表現出任何能改變這一現狀的徵兆。但是小牛卻從開局的混亂、傷病和漫無目的變成了結束時的團結、健康和目的明確的球隊。而當小牛第十次缺席季後賽的同時，他們已經開始品嘗勝利，並且期待在下賽季重回季後賽。
賽季後半段的30-18的戰績讓他們在1989-90賽季之後第一次取得了40勝，其中還包括了全聯盟最好的9-1的四月份戰績。
麥可-芬利是小牛能重建的基礎。這個6尺7的搖擺人上場時間是NBA所有人中最長的(42.2分鐘)，並且取得聯盟第十一名的得分和第二十的助攻。他打滿了所有82場比賽，讓他連續參加NBA比賽的場次增加到了379場，列NBA第二位。
芬利曾經是小牛重建的希望這個在NBA效力五年的球員取得了職業生涯最高的得分和籃板，並且取得了4次三雙，也是NBA僅有的四名20-5-5的球員之一。其他的三位是 凱文-加內特(KevinGarnett)， 格蘭特-希爾和 加里-佩頓(GaryPayton)。
德克-諾維茨基(DirkNowitzki)在他到NBA的第二個賽季有了長足的進步。他是小牛另外一個打滿所有比賽的球員。他的得分(17.5)，籃板(6.5)和上場時間(35.8)都是球隊第二。這個運動力不錯的七尺前鋒在三分線外的命中率高達37.9%，並且投中了NBA第15的116個三分球。在全明星周末里，他在三分球大賽中名列第二。
有了新的教練，年輕的核心，這一年的第12順位，以及 德爾-哈里斯(DelHarris)，赫德和前NBA巨星 希德尼-蒙克里夫(SidneyMoncrief)加入教練組，球迷的達拉斯的希望變的高了起來。
2000-2001：小牛用好成績告別老主場
小牛在99-00賽季的末期強勢爆發，看起來注定會在球隊在團聚球館(ReunionArena)的最後一年中繼續保持。2000-01賽季是小牛近10年以來最成功的一季，他們最終的戰績是53-29，也是他們近13年裡的第一次50勝。小牛的平均得分、命中率、罰球命中率和三分命中率都在NBA排名前五，而且他們還取得了球隊歷史最高的25個客場勝績。這些勝利的比賽直接帶來了小牛球隊歷史上第一個勝多負少的客場成績。另外，球隊對所有東部球隊都取得了至少一場勝利，這也是隊史第一次。
小牛在交易截至日之前做了一個爆炸性的交易，他們將休伯特-戴維斯(HubertDavis)，克里斯蒂安-萊特納(ChristianLaettner)，考特尼-亞歷山大(CourtneyAlexander)和伊唐-托馬斯(EtanThomas)送到奇才，換來了朱萬-霍華德(JuwanHoward)，Calvin Booth和ObinnaEkezie。
這比交易幫助球隊確保了球隊在西區第五的位置，並幫助球隊在11年以後重返季後賽，結束了NBA最長時間不進季後賽的紀錄。
作為西部賽區的的五號種子，小牛第一輪對陣的猶他爵士隊。在前兩場的比賽里他們以0-2落後，但是在主場進行的三、四場交鋒中，他們頑強的把比分扳成2-2，第五場比賽在猶他進行。
為了不讓爵士隊得到完全的主場優勢，馬克-庫班給那些願意前往猶他看球並且在身上圖上小牛隊顏色的球迷提供了免費的門票。令人吃驚的是，小牛在這場令人窒息的比賽中最終擊敗了爵士隊，比分是84-83，他們自1988年以來第一次打進分區季後賽的第二輪。由於這個系列賽的勝利，小牛成為了第六支在五局三勝賽制中，在0-2落後的局面下翻盤成功的球隊。
庫班的財大氣粗幾乎成為了小牛隊的象徵詞在第二輪季後賽中，小牛遇到的對手是州內的 聖安東尼奧馬刺隊。儘管小牛竭盡全力，但是強大的馬刺依舊以4-1將小牛淘汰。
除了球隊的勝利之外，還有一些個人的成就：
1: 麥可-芬利已經連續參加了461場比賽。
2: 德克-諾維茨基成為聯盟歷史上第二個單賽季投中100個以上三分(151)，並且送出100個以上火鍋(101)的球員。[上一個做到的是1995-96賽季的RobertHorry，他投中143個三分，有109次封蓋]
3: 德克-諾維茨基成為小牛隊歷史上第一個入選NBA最佳陣容級別的球員，他入選了第三隊。
4:體育畫報將球隊教練/總經理 唐-尼爾森選為年度最佳執行官，並且將 麥可-芬利和 德克-諾維茨基選入最佳第三隊。
當這個不可思議的賽季結束之後，小牛在團聚球館的時代畫上了一個完美的句號，他們期待在新家美航中心創造新的輝煌。
在00-01賽季定下了小牛籃球的基調之後，在2001-02賽季，他們將自己升格成了總冠軍的競爭者。賽季是在一個全新的，藝術級的美航中心內開始的，又一個打破紀錄的賽季即將啟程。
小牛取得了球隊歷史最好的57勝的戰績，並且成為了4支連續取得50勝的球隊之一。球隊同樣有38場比賽爆滿(隊史第四)。球隊12.1次的場均失誤是聯盟歷史最少的，打破了底特律活塞在1996-97賽季創下的紀錄。小牛同時也有NBA最好的客場成績，他們取得了27勝。而且他們在罰球命中率和平均得分上都名列聯盟第一，三分命中率也排名第四。
在二月，2002年的全明星賽在費城進行，小牛有兩名隊員和一名教練參與其中，隨後主教練唐-尼爾森帶領著他的得意門生德克-諾維茨基和史蒂夫-納什幫助西部以135-120戰勝東部隊。
連續第二個賽季，小牛在交易截至日之前做了大交易。這一次，他們送走了朱萬-霍華德(JuwanHoward)，蒂姆-哈達威(TimHardaway)和唐內爾-哈維(DonnellHarvey)，並從掘金得到了里夫-拉弗倫茨(RaefLaFrentz)，尼克-范艾克賽爾(NickVanExel)，塔里克-阿卜杜爾-瓦哈德(TariqAbdul-Wahad)和埃弗里-詹森(AveryJohnson)。
在以57-25的戰績結束常規賽之後，小牛排名中西部第二，在季後賽第一輪面對明尼蘇達森林狼隊。小牛在隊史上第一次橫掃了對手。球隊同時也創下了NBA歷史上五局三勝制里罰球命中率的新高(87.7%)。
在連續的第二個賽季里，小牛在第二輪碰到了西部領先的國王隊，他們連續第二年在第二輪折戟，比分同樣是1-4。
就像小牛隊整體一直在進步一樣，球員個人也在不斷努力著。
德克-諾維茨基保持著在常規賽和季後賽里穩定高效的發揮。在2月23日對國王隊的比賽里，他創下了當季單場防守籃板的紀錄(21個)。諾維茨基第二次入選了最佳陣容第三隊，並且第一次進入全明星陣容，他在1月21-27日期間當選了NBA當周最佳球員。他最終取得了38次兩雙。在季後賽第一輪中，他離NBA紀錄的43個籃板僅僅相差一個。並且繼卡里姆-阿卜杜爾-賈巴爾(KareemAbdul-Jabbar)之後成為1970年以來第一個在連續四場比賽中取得30+得分和15+籃板的球員。
史蒂夫-納什(SteveNash)入選了NBA最佳陣容，並且在NBA最快進步的票選中排名第三。他職業生涯第一次打滿了全部的82場常規賽，他也是小牛唯一完成這項任務的球員。同時，他也入選了全明星陣容，並且當選了12月10-16日的當周最佳球員。納什改賽季一共獲得了20次兩雙。
麥可-芬利在3月23日對灰熊的比賽中得到了他職業生涯的第10000分。他在4月8-14日當選NBA當周最佳球員。腿筋的傷病將芬利連續參加NBA常規賽的紀錄定格在了490場，這也是現役NBA球員中最高的紀錄。
里夫-拉弗倫茨成為了聯盟第三位投進100個三分和完成100次封蓋的球員。埃弗里-詹森成為NBA歷史上第五位為三支德克薩斯球隊都有過效力的球員，其他四人是查基-布朗(ChuckyBrown)，馬克-布萊恩特(MarkBryant)，維農-麥克斯維爾(VernonMaxwell)和大衛-伍德(DavidWood)。
主教練兼總經理唐-尼爾森第二次執教了全明星賽，並且成為繼蘭尼-威爾肯斯(LennyWilkens)和帕特-萊利(PatRiley)之後第三位千勝教頭。
這些對2002-03賽季的小牛意味著什麼呢？很顯然，美航中心走廊的盡頭有明亮的希望。當新賽季到來的時候，小牛將專注於繼續打破NBA紀錄，並且試圖贏下一切。
2002-03：小牛到達了新的高度
2002-03賽季的小牛把他們的定位定在了NBA強隊之一的行列，並且創造了多項球隊和個人的紀錄。在連勝14場的火熱開局之後，小牛取得了隊史最佳的60-22的常規賽戰績這也是球隊歷史上第九次勝多負少的賽季，同樣也使小牛成為NBA僅有的三支連續取得50勝以上戰績的球隊之一。小牛在3月中旬成為了第一支鎖定季後賽席位的球隊，他們在1988年以來第一次成為西部第一，最終以2-4敗在冠軍馬刺的腳下。小牛該季在季後賽里一共打了20場比賽，是隊史上最多的一次。
小牛是在執教了25年的唐-尼爾森教練的帶領下取得60-22的驕人戰績的。老尼爾森帶領著小牛在連續四個賽季中都取得了勝多負少的戰績。只有7個NBA教練達到過這么高的高度。老尼爾森曾經12次帶領所執教的球隊取得50勝，並且2次取得60勝。他在11月當選NBA當月最佳教練。
在唐-尼爾森的帶領下，小牛的三巨頭德克-諾維茨基，史蒂夫-納什和麥可-芬利再次爆發出強大的力量。德克繼馬克-阿吉雷之後成為小牛第二個單賽季得分上2000的球員。除了得到2011分之外，德克還展現了他的全能，在得分、籃板和搶斷上都是全隊第一。德克在來到小牛的五年中一直都在穩步的進步中。
史蒂夫-納什繼續證明自己是NBA的頂級控衛之一，他17.7的場均得分排名球隊第三，另外，他還是球隊的助攻王，平均能貢獻7.3次的助攻。這個賽季，他取得了職業生涯最高的罰球數、命中數、罰球命中率、搶斷和總蓋帽數據。納什以連續發中49次罰球創造了球隊的積累。他打破了現任球員發展教練羅蘭多-布萊克曼連續45次發中的紀錄。
三巨頭的第三人麥可-芬利在賽季中為小牛貢獻了出色的籃球。這位兩屆全明星的成員在為小牛效力期間取得了10000分的得分，成為了小牛歷史上得分第四高的球員。芬利場均貢獻19.3分，5.8個籃板和3次助攻，並且每場出場38.3分鐘。芬利同時也創造了個人生涯單場得分(42)，籃板(15)，三分命中(7)，罰球命中(15)和罰球數(17)上的最高紀錄。
由於他們正題的出色表現，諾維茨基，納什和芬利共同當選了NBA十一月的最佳球員。史蒂夫-納什和德克-諾維茨基連續兩年入選了NBA全明星陣容。
2002-03賽季小牛隊取得的好成績和他們華麗的打法也很好的刺激了球市，他們全部的11個主場都是爆滿的情況，這也是小牛自建隊以來的第一次。小牛從2001-02賽季以來連續71場主場門票售光。
在有了新的期待和目標之後，小牛在03-04賽季名正言順的成為了總冠軍的競爭者之一。
2003-2004：小牛從“三巨頭”變成"神奇五俠"
隨著新賽季的臨近，小牛希望在上賽季成功的基礎上再進一步。他們在賽季開始之前用尼克-范艾克賽爾，埃文-埃施邁爾(EvanEschmeyer)，波派-瓊斯，埃弗里-詹森以及安托萬-里加多(AntoineRigaudeau)到勇士換了安托萬-賈米森(AntawnJamison)，丹尼-福特森(DannyFortson)，基利-威爾斯(JiriWelsch)和克里斯-米爾斯(ChrisMills)。
在賽季開始一周之前，小牛用涉及了另一樁大交易，他們將里夫-拉弗倫茨，克里斯-米爾斯和基利-威爾斯送到凱爾特人，換來了安托萬-沃克(AntoineWalker)和托尼-德爾克(TonyDelk)。所有人都各就各位之後，小牛開始了他們對總冠軍的衝擊。
賽季的開始階段對正處在磨合期的小牛來說相當困難。但是小牛在一月到來的時候開始找到感覺，取得了九連勝。球隊把這一趨勢一直帶到了二月，他們在這個月裡取得了9-2的戰績，創造了球隊單月81.8%的最高勝率。
在賽季結束的時候，小牛連續第四個賽季進入了季後賽，並且在ESPN雜誌的球迷滿意度排名中位列所有運動隊的第二名。達拉斯擁有36-5的最佳主場戰績，並且第六次取得50勝以上的戰績，他們和湖人、國王以及馬刺一起成為了過去四個賽季都取得50勝以上戰績的球隊。
主教練唐-尼爾森再次帶領著球隊創造了一項項的紀錄。在2003-04賽季結束的時候，他已經擁有了13個50勝以上的賽季，平了菲爾-傑克遜(PhilJackson)的NBA第二高紀錄。在2003年11月11日，老尼爾森執教了他來到小牛之後的第250場比賽。同年12月15日，他贏得了個人的第1111場比賽，超過帕特-萊利(PatRiley)成為NBA勝場第二多的教練。
小牛的“三巨頭”再次成為球隊的重要貢獻者。納什是球隊得分榜的第四名，並且取得了職業生涯最高的場均8.8次助攻。全聯盟中，他的91.6%的罰球命中率排名第二，助攻和三分命中率都排名第三。他同時也在11月12日對陣開拓者的比賽中取得他職業生涯的第一個三雙，14分12次助攻和職業生涯最高的10個籃板。
德克-諾維茨基繼續統治著球隊得分，籃板，搶斷和蓋帽上第一的位置。德克入選了NBA最佳陣容第三隊，這也是他第四次獲此殊榮。二月，德克也連續第三次作為替補參加了全明星賽。這對一個進聯盟僅僅6年的球員來說是個不壞的成績。
芬利一如既往的可靠，以38.6分鐘的上場時間成為球隊最勤奮的人，並且在得分和搶斷榜上都名列球隊第二。同時，他也投進了150個三分球，超過了他上賽季剛剛創造的119個的個人紀錄。在一月中旬，他被評為一周西部最佳球員。
小牛的兩個新兵賈米森和沃克同樣在賽季里證明著自己的價值。賈米森當選年度最佳第六人，是繼羅伊-塔普利之後小牛唯一獲此殊榮的球員。賈米森參加了全部的82場比賽，將當時NBA球員連續參賽場次的紀錄增加到328場。他同樣也有職業生涯最高的53.3%的投籃命中率，這在聯盟也排名第三。
安托萬-沃克同樣也證明著自己。他是繼傑森-基德之後第一個在連續兩場比賽中打出三雙的小牛球員(1月12日對紐約和1月14日對76人)。沃克的8.3個籃板和5.4次助攻都排在球隊第二，他的得分排在球隊第五。同時他也是小牛唯一先發全部82場比賽的球員。
兩名新秀，約什-霍華德(JoshHoward)和馬奎斯-丹尼爾斯(MarquisDaniels)成為了球迷的最愛，並且也對球隊做出巨大的貢獻。他們都入選了NBA最佳新秀第二隊(是小牛繼基德之後第一次有新秀入選最佳陣容)。霍華德同時還參加了全明星周末的新秀挑戰賽。在NBA的所有新秀里，他的得分排在第七而籃板排到第五。丹尼爾斯，他在賽季的最後11場比賽中平均得到20.7分，最終場均得分列新秀第八，而49.4％的投籃命中率則超過了所有同屆進入NBA的其他菜鳥。
儘管他們因為在第一輪輸給國王而比預期提前結束了賽季，但是小牛證明他們已經成為一股不可忽視的力量，並且也顯示了良好的上升勢頭。小牛的球迷有理由期待04-05賽季球隊會取得成功，希望他們能比從前走的都要遠。
2004-2005：改…改…改變
在2004-05賽季之前，小牛進行了幾個主要的陣容調整。在三個不同的交易中，小牛得到了傑里-斯塔克豪斯(JerryStackhouse)，選秀第五順位(他們用它得到了新秀控衛德文-哈里斯(DevinHarris)，傑森-特里，阿蘭-亨德森(AlanHenderson)和埃里克-丹皮爾(ErickDampier)。在得到這些球員的同時，小牛也失去了安托萬-賈米森，安托萬-沃克和埃東多-納胡拉(EduardoNajera)，同時，他們還在自有球員市場上失去了史蒂夫-納什。
在場上，小牛的第25個賽季被證明時另一個成功的賽季。他們以58-24結束常規賽，球隊史上第二好的成績。球隊連續第五年打進季後賽，平了球隊最長連續打進季後賽的紀錄(1984-1988)。
在球隊陣容發生變化的同時，在賽季後期，球隊的主教練也有了變化。在3月19日的比賽之前，唐-尼爾森辭去了小牛主教練的職務，轉而成為球隊的顧問。尼爾森將接力棒交到了埃弗里-詹森的手裡，他成為了小牛歷史上第八位主教練。在他執教的18場常規賽比賽中，詹森帶隊取得了令人吃驚的16-2的戰績。
在作為小牛主教練的8個賽季中，老尼爾森成為球隊最成功的教練，他取得了總共339-251的戰績，勝率達到57.5%。在他的生涯中，他執教了2070場比賽(1190-880)，這個戰績讓他成為NBA歷史上獲勝場次第二多的教練。
儘管在前兩場中失利，小牛隊還是在西部季後賽的第一輪淘汰了火箭隊，他第七場決勝中，他們40分的優勢也是NBA季後賽歷史上的最大分差。這也讓他們成為了NBA歷史上第九支在0-2落後的情況下在七局四勝制比賽中反敗為勝的球隊，並且是在主場輸掉兩場比賽後反敗為勝的第三支球隊。
儘管在第二輪中輸給鳳凰城太陽，小牛的賽季依然很成功，對於球隊和個人都是這樣。在4月5日的勝利之後，小牛再次獲得50勝，和國王以及馬刺一起成為NBA僅有的3支在過去5個賽季中都取得50場以上勝績的球隊。
德克-諾維茨基成為了僅有的6名在過去五個賽季都入選NBA最佳陣容的球員。他同時也是第一個入選NBA最佳陣容第一隊的歐洲球員(也是第一個沒有在美國上高中或者大學的球員)。在12月2日對火箭的比賽當中，德克得到53分，這創造了新球館、個人和隊史的最高紀錄。在這個賽季里，德克的總得分再次過2000，並且在場均得分(26.2)、助攻(3.1)和封蓋(1.53)上都創下個人新高，最終在MVP的投票中排名第三。
在3月26日對騎士的比賽中，麥可-芬利令人吃驚的在三分線外8投8中。他不僅改寫了個人單場三分最多命中數的紀錄、平了球隊在沒有加時的比賽中三分的最多命中數，並且還改寫了球隊歷史上單場比賽連續投進三分的新紀錄。
新秀德文-哈里斯在11月當選該月西部最佳新秀，成為小牛自1995年以來第一個獲此殊榮的球員。
隨著埃弗里-詹森的時代正是到來，以及球隊在陣容上做的合理調整，小牛有理由繼續對接下來的2005-06賽季感到興奮。
2005-2009:坎坷爭冠路
2005-2006:離夢想只有一步
或許沒有人想到，之前只有一次打入西區決賽經歷的小牛，之前連續兩年止步半決賽的他們，突然就完成了衝出西區的夢想。是的，庫班的面前不再會看到沙克在面前晃悠，而鄧肯這座大山也終於被翻越了。即便有舊將納什領軍的太陽最後攔路，也絲毫不能阻擋這隻已經自信滿滿的奔牛，球隊歷史上首奪西區聯盟冠軍，終於圓了25年來的總決賽夢想。
這個賽季小牛終於告別了唐-尼爾森（Don Nelson）時代,進入了小將軍埃弗里-詹森（Avery Johnson）時代,小將軍帶給球隊的是全新的風格，球隊在沒有放棄進攻的前提下，加強了防守上的重視度。這隻攻守兼備的球隊在02-03賽季後再度在常規賽中拿下60勝，而那個賽季他們也進入了西區決賽。
除了諾維斯基外，兩位球隊新星約什-霍華德（Josh Howard）以及馬奎斯-丹尼爾斯（MarquisDaniels）逐漸成長為了球隊新生代的希望。而另兩位老球皮傑森-特里（Jason Terry）和斯塔克豪斯依舊扮演著無解搶分狂的角色。
季後賽首輪的對手是同分區的孟菲斯灰熊隊，顯然這個球隊無法給小牛的鐵騎帶來任何阻礙。一個乾淨利落的4：0,然後站在小牛面前的就是老冤家，同區的聖安東尼奧馬刺隊。
馬刺隊結束了一個堪稱完美的賽季，63勝甚至比小牛隊還來的出色，也是馬刺隊歷史常規賽最佳戰績，然而這樣一個幾乎無懈可擊的衛冕冠軍，卻在小牛隊面前吃盡了苦頭，雙方展開了一次載入史冊的季後賽較量。
諾維斯基毫無疑問是球隊的支柱球員，在第一場客場失利後，他率領了球隊在接下來一鼓作氣取得了三連勝的佳績，他展現了少有的衝擊力和取勝欲望，第三場甚至24次走上了罰球線，馬刺隊隨後連扳兩場，雙方不得不進入第七場的決戰。這一場比賽幾乎成了諾維斯基和鄧肯的對飈大戰，在第四節結束前，一整場發揮都極其出色的馬努-吉諾比利對諾維斯基的突破下手犯規，結果諾維斯基上籃命中還取得加罰，一舉拖入加時賽。而加時賽中迪奧普遏制了鄧肯的發揮，最終拿下37分的諾維斯基戰勝了拿下41分的鄧肯，而面對他的則是老朋友，史蒂夫-納什率領的太陽隊。
小牛和太陽各在對方主場拿下一場勝利，比賽迎來了天王山戰役，結果諾維斯基在這場比賽中轟下了職業生涯季後賽新高的50分，幫助球隊擊敗了太陽隊，最終球隊4:2勝出，而總決賽的對手，則是東區新貴熱火隊。
雖然庫班和小牛隊過去幾年一直害怕大鯊魚奧尼爾，但是總決賽一開始的兩場比賽卻給了小牛隊十足的信心，奧尼爾狀態不佳，而在特里和斯塔克豪斯的幫助下，球隊在主場取得了兩連勝。第三場最後第四節還有7分鐘時球隊還保持兩位數的領先，但是隨後韋德一己之力帶領熱火打出高潮，最後時刻諾維斯基錯失關鍵罰球，球隊2分落敗。此役過後，熱火眾將逐漸找回感覺，佩頓，莫寧，沃克等人都有獨當一面的發揮，而韋德更是展現了新一代球星的風采，最終球隊連拿四場，小牛不得不飲恨而歸。
2006-2007:捲土重來慘遭黑八
雖然在總決賽上失利，但是新的賽季沒有人會認為這隻去年的西區新貴會有任何的實力下滑。球隊在休賽期送走了丹尼爾斯，全力扶持 約什-霍華德（JoshHoward）。而後者也不負眾望，在這個賽季，他能場均貢獻18.9分，6.8個籃板，成為了諾維斯基身邊最得力的助手，而他也在這一年入選了NBA全明星。至於球隊領袖諾維斯基則表現更是穩定，24.6分，8.9個籃板雖然不是他職業生涯最佳表現，但是球隊卻在他的帶領下一路狂飆，整個賽季拉出了3次十場以上的連勝，其中包括一個16連勝。球隊在小將軍 埃弗里-詹森（AveryJohnson）的調教下達到了隊史最佳狀態，常規賽67勝的第一名戰績讓所有人都對他們報以期待。
然而一切都過於順利了，小牛隊發現自己的季後賽首輪對手就是前任主帥唐-尼爾森(Don Nelson)率領的金州勇士隊，勇士隊在賽季末拉出了一波9勝1負的戰績衝進季後賽，狀態咄咄逼人，尤其是他們曾經終結了小牛隊的16連勝。小將軍詹森不敢怠慢，在季後賽開始的時候讓老將德文-喬治（Devin George）頂替埃里克-丹皮爾（Eric Dampier）出任 先發，用小個陣容與勇士的跑轟對抗。結果畫虎不成反類犬，第一場比賽勇士就給常規賽第一一個下馬威，巴朗-戴維斯（Baron Davis）轟下33分14板8助攻，小牛全隊對他束手無策。雖然第二場比賽小牛扳回一局，但是到了金州勇士主場後，所有人都被甲骨文球館瘋狂的金色海洋震撼了，勇士隊打出了最激情的炮轟連勝兩場，雖然第五場達拉斯在主場扳回一局，但是第六場比賽勇士隊在史蒂芬-傑克遜（Stephen Jackson）的帶領下全線開火，小牛無奈只好接受出局的現實，他們也成為了自從實行首輪7戰4勝制後第一個被淘汰的分區第一。
稍微可以值得安慰的一件事情，是諾維斯基最終在評選中戰勝了納什，當選了年度常規賽MVP。然而他不得不身著西裝在發布會室內領獎，而不是站在季後賽的球場中了。
2007-2008:重新上路，再遭重創
雖然上個賽季首輪慘遭黑八淘汰，但是小牛隊似乎並不認為球隊需要做什麼改變，小將軍詹森繼續留任，而球隊的主要得分手也沒有任何改變。球隊補強中最明顯的應該是從黃蜂隊簽來的05級2輪新秀布蘭登-巴斯（Brandon Bass）。然而賽季開始後，球隊再也沒法找回去年那種霸氣，球隊始終戰績難以起色。眼見形勢不妙，庫班在交易截止日期前終於忍痛放棄了培養數年的新星控位德文-哈里斯（Devin Harris）而從新澤西籃網隊迎回了球隊舊將賈森-基德（Jason Kidd）希望憑藉基德的經驗給這個球隊帶來新的變化。
可惜基德也沒有很快融入這個球隊，畢竟季中交易控位是一件很冒險的事情，球隊最後僅僅以51勝結束常規賽，在競爭激烈的西區這個成績也只能位列8強後半段。失去了首輪主場優勢，小牛在與黃蜂隊的較量中完全處於下風，僅僅在第三場主場拿下一場勝利，其餘比賽幾乎無法給對手帶來什麼威脅。無奈只有接受連續第二年首輪出局的結果。
2008-2009:換帥難求進步
連續兩年季後賽悲慘失利，球隊終於炒掉了 埃弗里-詹森（Avery Johnson），然後聘請了前步行者隊主帥 里克-卡萊爾（RickCarlisle）執掌教鞭。球隊的主體陣容依舊沒有什麼改變，但是巴斯和巴里亞等新人開始逐漸成長成為球隊重要輪換球員。可惜卡萊爾也沒有化腐朽為神奇的能力，球隊的常規賽戰績甚至比去年還少勝一場。球隊主力球員的老齡化問題也開始侵擾球隊的狀態穩定性，基德不再年輕，而斯塔克豪斯的狀態急劇下滑。唯一的例外是 傑森-特里（Jason Terry），他在卡萊爾的手下再次煥發了第二春，安排在替補席上出場的特里賽季接近能砍下場均20分，憑藉恐怖的得分爆發力，特里也榮膺了本賽季NBA最佳第六人。
球隊在季後賽首輪的對手是老冤家 聖安東尼奧馬刺隊，雖然對手手握主場優勢，但是陣中主將馬努-吉諾比利（Manu Ginobili）賽季報銷讓馬刺戰力受損。即便在諾維斯基狀態不佳的情況下，依靠霍華德和特里的出色發揮，小牛在客場偷得一勝，回到主場又連下兩城，最後的第五場大戰，諾維斯基終於爆發，砍下30分幫助球隊淘汰了馬刺隊。
西區半決賽小牛遇到了本賽季進步巨大的 丹佛掘金隊，掘金隊在昌西-比盧普斯的率領下一路高歌猛進，不進常規賽發揮出色，季後賽也保持著驚人的狀態。小牛隊面對掘金的超強火力難以招架，客場連輸兩局，關鍵的第三場比賽，小牛在最後時刻還領先2分，安托萬-萊特試圖對 卡梅隆-安東尼（Carmelo Anthony）戰術犯規，但是裁判沒有吹哨，安東尼抓住機會投出絕殺三分，幫助掘金客場一分險勝，系列賽3:0領先。小牛回天乏力，最終1:4被掘金淘汰。
2009-10：不穩定和大交易
賽季前續約傑森-基德，用一筆大交易換來了肖恩-馬里昂，又簽下蒂姆-托馬斯和德魯-古登這兩位有經驗的老將，約什-霍華德傷愈復出，小牛隊看上去在新賽季將大有作為。從賽季初到12月末，小牛一路順風順水，取得了34勝14負的驕人。但進入1月份後，球隊開始進入低谷期，僅僅取得10勝11負的戰績，從西部第二跌落至西部第四，球隊低迷表現促成球隊進行了兩筆交易：先是從籃網交易來防守尖兵納胡拉，2月份又送出 約什-霍華德， 德魯-古登和昆廷-羅斯從奇才換來了 卡隆-巴特勒， 布蘭登-海伍德和德肖恩-史蒂文森。這次交易帶來的效果非常明顯，除了第一場對雷霆失利外，小牛迎來了久違的十三連勝，重返西部第二，當家球星德克-諾維斯基更是蟬聯西部周最佳球員。但是隨後陷入小傷小病的困擾，更是在主場大敗紐約34分，球隊再次回歸平庸，帶著55勝27負西部第二的戰績進入季後賽。
諾維斯基的小牛隊有天賦但是總是缺少點什麼小牛隊季後賽首個對手是同區的馬刺隊。首場比賽“德國戰車”就轟下36分，加之賽季中加入的巴特勒也表現出色砍下22分，小牛隊主場退敵。第二場比賽，儘管諾維斯基一如既往穩定拿下24分，替補席上特里更是砍下全隊最高27分，但是馬刺“四巨頭”合力拿下83分，小牛無奈只能接受主場失利的事實。第三場比賽來到馬刺主場進行，小牛首發除了諾維斯基砍下35分外，無一人得分上雙，要不是替補席上特里和巴里亞分別砍下17分和14分比賽恐怕早早失去懸念，最終馬刺依靠帕克最後時刻連續進球取得勝利。第四場比賽依然在馬刺主場進行，正好球隊球星鄧肯也迎來自己34歲生日，不過本場比賽鄧肯表現低迷，9投1中僅僅取得4分，小牛隊第二節單節31-17，帶著11分的領先優勢進入下半場，馬刺第三節依靠強硬的防守讓小牛隊僅僅得了11分，馬刺單節砍下29分，完成反超，雖然小牛苦苦追趕，但是馬刺憑藉小將 喬治-希爾的29分的表現，再次主場擒敵。第五場比賽回到美航中心，逼上絕路的小牛背水一戰，巴特勒全場貢獻35分，小牛103-81將全場夢遊的馬刺隊打回聖安東尼奧。最後一場比賽回到主場的馬刺早早確立了22分的領先優勢，但是諾維斯基幾乎憑藉一己之力將比分反超，但是除了他和巴特勒和替補席上布博瓦外，小牛沒有人得分上雙，最終馬刺憑藉整體發揮擊敗小牛，上演“黑七”。
