1999-2000赛季小牛队看到了复兴的曙光。常规赛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淘汰，成就了对方的黑八奇迹。当家球星德克.诺维茨基获本赛季常规赛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支季后赛遭横扫的卫冕冠军。2月27日，达拉斯小牛队在客场以84比90不敌孟菲斯灰熊队。北京时间3月11日，达拉斯小牛队（29胜33负）在客场保持连胜势头。卡特替补得到22分和9个篮板，诺维茨基得到16分和9个篮板，他们率队四人得分上双，小牛队在二三节发力把比分差距拉开，他们在客场以100-77轻取明尼苏达森林狼队（21胜39负）。小牛队取得三连胜，森林狼队遭遇两连败。2012至2013赛季2013年04月11日达拉斯小牛队主场91:102负于菲尼克斯太阳队，残存的一丝晋级季后赛希望彻底破灭，这是13年来小牛首次无缘季后赛，上一次在4月初就迎来假期，小牛要追溯到2000年。这一切对于库班和整个达拉斯来讲，都有些陌生，对于普通人来讲，陌生来临必然需要些许时间来适应。而小牛队老板马克-库班基本没有任何过度，直接适应这种陌生，明确表示他希望这样糟糕的赛季会是小牛最后一次经历，“我总是和球队强调一个赛季只有一个总冠军，我们球队的目标只有总冠军，所以这一次失败很让人沮丧，但是困难不会打倒我们，我们会东山再起。”小牛上一次夺冠就在两年前，但物是人非,夺冠赛季结束的夏天，库班选择将夺冠肱骨之臣泰森-钱德勒和何塞-巴里亚进行交易，库班本来是打算腾出薪金空间，能够在夏天交易市场网罗一条大鱼，以便和诺维茨基一同带领小牛再一次冲击总冠军，但是算盘失手，小牛连续两个赛季错过克里斯-保罗、德怀特-霍华德和德隆-威廉姆斯，靠小手笔交易得来卡曼、布兰德、梅奥和科里森一批不错的球员，但是这些球员还不足以拼起达拉斯的总冠军宏图。而这两个赛季特别是本赛季，小牛一塌糊涂，从总冠军沦为平民球队仅仅用了两年的时间，再回首那个夏天，更像昙花在傍晚夕阳中，除了美好还有惋惜。以库班的行事风格，这个夏天小牛必然会进行重建，核心还是诺维茨基，然后伺机网罗一条大鱼。保罗和霍华德都将在这个夏天合同到期，但是以现在的情形看，快船和湖人不太可能选择放走两位建队核心，所以小牛得到他们的可能性和在夏天的选秀中抽到状元签的可能性差不多。而对于德隆-威廉姆斯，库班已经表示没有德隆，小牛会变得更好，怎么听这都有些政治语言的修饰意味。很有可能在这个夏天得不到一位和诺维茨基一起带领小牛复兴的巨星，但是库班依旧信心爆满，“相信我，我们球队会做一些事情的。”这个话是库班说给诺维茨基听的，他要努力再争取一位巨星，从而留住诺天王的心。这些口头上的东西不能代表什么，现在库班唯一能做出的承诺是，“我们球队将抓住机会，倾其所能地做好我们能做的。”现在摆在小牛面前的任务是和诺维茨基续约，诺维茨基已经表示他希望能够和小牛续约2年或者更好时间，从而能够终老达拉斯，这就意味着新的合同他会接受少于上个合同最后一年2300万美元的合同。库班表示，“德克职业生涯的黄金岁月都献给了我们球队，我们球队也获得了总冠军，接下来我们要在德克的第二段黄金时光做更多的事情，争取下一个总冠军，这就是我们一直努力在做的事情。”
