公牛王朝时代

在1995-96赛季前，罗德曼被格雷格·波波維奇賤賣到了芝加哥公牛，馬刺队則得到中锋威尔·普度（Will Perdue）和其他的优惠。對此罗德曼非常生氣，當交易成立時他直言：「馬刺拿我換一個不會打球的傢伙，可見非常怨恨我、想擺脫我，我一點也不覺得受到侮辱，受到侮辱的應該是馬刺隊，我不管馬刺隊拿我換什麼，我只想離開聖安東尼奧，並讓他們後悔笑不出來！」

絕大部分球迷對罗德曼言論抱著恥笑態度，同時亦期待他令公牛自我毀滅，畢竟當初罗德曼在活塞時期和公牛的迈克尔·乔丹、斯科蒂·皮蓬處於老死不相往來敵對情況，每次對壘都是打架多過打球，罗德曼各種黑手、小動作令他們深惡痛絕，而迈克尔·乔丹在NBA世界中人人都尊稱他為「神」，而罗德曼則是人見人憎的「惡魔」。

結果在1995-96赛季，公牛不僅沒有毀滅，戰績反而更加提升，罗德曼完美地融入公牛的三角戰術，乔丹更稱從來沒見過有誰(罗德曼)能夠那麼快便學會公牛隊複雜的進攻戰術﹐連他都沒想過自己和乔丹手攜手合作能夠徹底反轉全世界，将公牛的胜绩从前一年的47胜35负到72胜10负，提高了整整25场比赛的胜利。球队中的罗德曼、乔丹和皮蓬都荣登那一年的全明星最佳防守第一隊阵容，这也是NBA历史上第一次有三位同队球员入选同一年的最佳防守第一隊，罗德曼连续第五年抓得全联盟最高的篮板数，乔丹的得分则是全联盟最高的，这也是NBA历史上第二次同一个队的两位球员夺得全联盟的最高得分和篮板球。

在季後賽公牛更是無法阻擋，第一輪3-0輕取阿朗佐·莫寧在陣的熱火；第二輪4-1擊退派屈克·尤英率領的紐約尼克；在東區決賽對手是去年令公牛飲恨的奧蘭多魔術，由兩大王牌「一分錢」安芬尼·哈德威和「大鯊魚」沙奎尔·奥尼尔率領，加上擁有攻守不俗第一代公牛王朝第三號人物霍雷斯·格蘭特﹐他熟識公牛的戰術打法。賽前預測會是一場激烈比拼﹐第一場安芬尼·哈德威和沙奎尔·奥尼尔分別拿下最高38分和27分，但是全隊合共只拿83分，得分第三名的布萊恩·肖只得5分，而罗德曼完全封鎖了霍雷斯·格蘭特，令其28分鐘僅1投0中、1籃板，其後更受傷離場系列賽報銷，更精彩的是同時成功以203公分身高、107公斤的身材去箝制216公分、150公斤的「大鲨鱼」奥尼尔，絕對是公牛橫掃魔術的功臣。

總決賽對手是西雅图超音速，公牛以4比2令對手臣服，亦是歷年罗德曼打得最出色的總決賽，場均7.5分14.7篮板，看似平平無奇，但實際比賽內容極其出色，出色到唯一一次出現有大量球迷(包括公牛球迷)質疑為何是迈克尔·乔丹拿下NBA总决赛最有价值球员(雖然六場比賽乔丹場均27.3分、5.3籃板、4.2助攻、1.7抄截、投籃命中率41.5%，但是在最後三場表現差劣，更出現31.6%和26.3%命中率，原因在於在最後三場改由加里·佩顿對位防守)而不是屬於罗德曼，罗德曼在六場比賽中有三場進攻籃板比防守籃板還多，更有兩場搶下十一個進攻籃板平了NBA總決賽最佳記錄，至今仍然無人能打破，在第二場搶下十一個進攻籃板(前後合共二十個)，替公牛克服了全場39%的投籃命中率，加上當時公牛在剩下8.9秒領先3分，其中尚有兩次罰球機會，然而斯科蒂·皮蓬竟然兩罰全失，之後罗德曼同萨姆·帕金斯一齊搶球變成爭球，爭球亦不相上下，混亂中罗德曼被德特夫·史伦夫犯規而走上罰球線，頭一球射失；第二球射入得以將分差拉開到四分；第六場在領先三比二情況下的再一次搶下十一個進攻籃板(前後合共十九個)將公牛送上冠軍舞台。

比賽中除了瘋狂的籃板球數量，還將自己所有擅長技能發揮到最大極限，惟妙惟肖的假摔、遊走在灰色地帶的小動作、強硬的防守，完完全全地將西雅图超音速球員搞得一塌糊塗、不得安寧，外線的加里·佩顿被小動作糾纏反被吹犯規，向球證抱怨換來技術犯規，需要隊友安撫情緒；文森特·艾斯丘被進攻籃板氣得責罵隊友；德特夫·史伦夫同樣在進攻籃板加上多次被製造進攻犯規在暫停時踢椅子來洩憤；而最大受害者分別是弗兰克·布里克考斯基和肖恩·坎普，場場都被罗德曼搞得氣急敗壞、狼狽不堪卻又無可奈何只能苦笑連連，前者在第一場比賽只是上場短短兩分鐘就被製造一級故意犯規再追加技術犯規迅速地離場；到了第三場在乔丹罰球時突然被滿面笑容看著，之後幾回合的攻防被製造二級故意犯規，後者第一場關鍵時刻被小動作糾纏，之後大動作反擊被吹第六犯離場。之後每場都經常被製造犯規，第六場也六犯離場，平均每場有4.6次犯規。

當時西雅图超音速教練乔治·卡尔在總決賽完結後講出以下兩段話：「籃下每當大家要準備搶籃板之時，一顆五顏六色的頭就會忽然升空，並將球搶入自己的雙手裡，這實在是讓我們感到無比的頭痛。」、「當你評估系列賽時，我不知道誰是MVP，但是丹尼斯·罗德曼嬴下兩場比賽，丹尼斯·罗德曼是他們(公牛)成功(拿下NBA總冠軍)的原因。」

當時公牛正在歡天喜地慶祝，其中有記者訪問迈克尔·乔丹，內容大致是「丹尼斯·羅德曼有同你競爭NBA总决赛最有价值球员的可能嗎？」而全世界公認好勝心、不服輸方面無人能出其右的迈克尔·乔丹回答：「毫無疑問地我認為他絕對有這個資格，他的表現實在是太驚人！」但最終迈克尔·乔丹還是以5票打敗肖恩·坎普的3票和丹尼斯·羅德曼的2票拿下NBA总决赛最有价值球员，同時亦是他籃球生涯中拿下六次NBA总决赛最有价值球员最具爭議性的一次。

罗德曼在之后的1997和1998年又幫助公牛蝉联了总冠军，取得3连冠的伟业。

罗德曼以球场出格的行为所被大家熟知，著名的有1996年4月16日在一场比赛中因不服裁判Ted Bernhardt的判决而发生争执，之后他头槌Bernhardt，事发后惹起了不小风波，罗德曼被联盟罚款25,000美金和禁赛五场[4]。另一个丑闻发生在1997年1月15日与明尼苏达森林狼队的比赛中。当时罗德曼在一次拼抢篮板过程中脚下拌蒜撞到了场外的摄影师Eugene Amos，摔倒后心存不满的罗德曼往摄影师的腹股沟踢了一脚[5]。尽管罗德曼马上被处以技术犯规一次，最后罗德曼被处以补偿摄影师Eugene Amos损失费200,000美金以及联盟的11场禁赛，这是当时联盟最长的禁赛纪录。

罗德曼在1997-98赛季后离开公牛队，公牛也因乔丹的第二次退役和斯科蒂·皮蓬的离去而进入了重建阶段。与此同时罗德曼也结束了他最后一个重要的NBA赛季，之后的他只是短暂有限的出现在其他的NBA球队中。罗德曼是NBA90年代最出色的篮板手，连续7年取得篮板王头衔，他在防守方面足以应付从迈克尔·乔丹、斯科蒂·皮蓬、魔术师约翰逊和拉里·伯德这样的外线攻击手到沙奎尔·奥尼尔、阿伦佐·莫宁、肖恩·坎普、卡尔·马龙、查尔斯·巴克利这样的强力内线。