1977-78赛季，公牛队战绩略有下滑，虽然全明星赛前取得了28胜23负的战绩，但整个赛季却只取得了40胜42负的战绩，无缘季后赛。吉尔默那一年代表公牛队参加了全明星赛，这也是他随公牛队首次全明星之旅，在公牛队六年的职业生涯中他四次入选全明星阵容。这个赛季他场均可以得到22.9分、13.1个篮板，55.9%的投篮命中率位列联盟第三。
公牛队在接下来的一个赛季每况愈下，战绩为31胜51负。这个赛季公牛队更换了两位主教练，拉里·科斯特洛在赛季开始前接替艾德·罗伯逊，但在取得20胜36负的开局后不得不被解雇。斯科蒂·罗伯逊接任，但在赛季剩余的比赛中只取得了11胜15负的成绩。吉尔默仍然是球队的头号得分手，场均得到23.7分和12.7个篮板，这两项数据不仅是队内最高，也排在整个联盟的前十名。出色的后卫特乌斯是1978年第一轮被公牛队选中的球员，他入选了该赛季的最佳新秀阵容，开始了他13个赛季的职业生涯。
1979-80赛季，公牛队战绩更糟，仅取得30胜52负。杰里·斯隆成为球队新任主教练，他自1976年退役后一直担任球队球探和助理教练。斯隆的第一个赛季恰逢吉尔默腿伤，他缺席了前34场比赛，结束了自己670场的连续出场纪录。
1980-81赛季，公牛队降级至中部赛区，为新加入的中西部赛区的达拉斯小牛队腾出空间。新赛区对公牛队十分有利，战绩反弹至45胜37负，排在密尔沃基雄鹿队的60胜22负之后。本赛季公牛队的胜率一直在50%左右徘徊nba历史单赛季最糟糕的战绩纪录，但在赛季末打出高潮，15场比赛取得13胜2负的战绩。公牛队自1977年以来首次重返季后赛。季后赛首轮，公牛队以三局两胜制2-1击败纽约尼克斯队，但在东部半决赛中被凯尔特人队以4-0横扫，凯尔特人队夺得赛季冠军。
1981-84：三年的苦难
公牛队在 1981 年的选秀中选中了身高 6 英尺 9 英寸、来自圣母大学的前锋奥兰多·沃尔里奇。尽管在赛季开始前一切看起来都很有希望，但 1981-82 赛季却令人失望。12 月 2 日，公牛队与勇士队打了一场奇怪的比赛，尽管投篮命中率高达 70.5%，却以 119-120 输掉比赛，打破了球队的记录。在主教练杰里·斯隆的带领下，公牛队取得了 19 胜 32 负的战绩，公牛队总经理罗德·索恩于 2 月 17 日取代斯隆担任主教练。在索恩的带领下，公牛队在赛季剩余时间取得了 15 胜 15 负的战绩，最终以 34 胜 48 负的战绩结束了赛季。吉尔默仍然是球队的统计数据领先者，场均得到 18.5 分和 10.2 个篮板nba历史单赛季最糟糕的战绩纪录，他的 65.2% 投篮命中率位居联盟第一。
在经历了一个令人失望的赛季后，公牛队开始调整球队阵容。1982 年，公牛队选中了身高 6 英尺 3 英寸（1.91 米）的后卫昆汀·戴利，他来自旧金山大学，才华横溢但问题重重。公牛队还将球队的头号球星阿蒂斯·吉尔默交易给了圣安东尼奥马刺队，换来了戴夫·克雷恩和马克·奥尔伯丁。
1982-83赛季，公牛队战绩每况愈下，在新教练保罗·韦斯特海德的带领下仅取得28胜54负的成绩。韦斯特海德曾在1980年率领洛杉矶湖人队夺得NBA总冠军。公牛队开局不利，客场连败7场。沃尔里奇的膝伤让他缺席了最后的25场比赛，球队再次遭遇7连败。本赛季雷吉·塞斯场均得到23.8分，入选全明星阵容，新秀昆汀·戴利场均得到15.1分，入选最佳新秀阵容。不过保罗·韦斯特海德的执教时间并不长，赛季结束后合同期内被解雇。
1983-84赛季，凯文·洛维尔开始执教公牛队，但只取得了27胜55负的成绩，是队史第二差的战绩。赛季中期，公牛队将苏斯交易给堪萨斯城国王队，换来史蒂夫·约翰逊和选秀权，为日后挑选得分后卫创造了机会。
1984-87：“飞人乔丹”
第三顺位选秀权让这个惨淡的赛季松了一口气。休斯顿火箭队拥有第一顺位选秀权，他们选中了哈基姆·奥拉朱旺，这位大个子在十年内一直主宰着中锋位置，也是历史上最具统治力的中锋之一。波特兰开拓者队用第二顺位选中了另一位中锋萨姆·鲍伊，但他的职业生涯因伤病而中断。公牛队用第三顺位选中了来自北卡罗来纳大学的身高 6 尺 6 寸的后卫迈克尔·乔丹。
1984-85赛季，乔丹直接进入首发，公牛战绩提升至38胜44负，乔丹开始改写公牛的新篇章。2月12日，乔丹在公牛对阵活塞的比赛中砍下新秀最高的49分，创下新秀单场得分记录。乔丹整个赛季表现惊艳，并获得了1985年全明星赛首发资格。很多人把乔丹和朱利叶斯欧文比较，因为他们两人都是在篮筐之上打球的人。乔丹本赛季场均得到28.2分，仅次于尼克斯队的伯纳德金（32.9分）和凯尔特人队的拉里伯德（28.7分）。此外，乔丹在篮板（6.5个）、助攻（5.9个）和抢断（赛季共196个）方面均位居第一。 赛季结束后，他获得了联盟最佳新秀奖。
乔丹帮助公牛队自 1981 年以来首次重返季后赛，但季后赛并没有持续太久，公牛队在第一轮就以 1-3 输给了密尔沃基雄鹿队。主教练洛夫里在赛季结束后被解雇。
1985-1986赛季，斯坦·阿尔贝克被任命为球队新任主教练。不幸的是，在赛季第三场比赛中，乔丹摔断了脚，很多人预计他将缺席赛季剩余比赛，但乔丹在3月15日康复，并帮助公牛队以30胜52负的战绩搭上了季后赛的末班车。最终，乔丹本赛季缺席了64场常规赛。
公牛队首轮迎战实力强大的波士顿凯尔特人队，0-3惨遭横扫。不过，乔丹在波士顿花园第二场比赛中砍下63分的壮举将载入史册。比赛经过两个加时赛，最终凯尔特人队以135-131获胜。乔丹单场63分创下了季后赛得分纪录，至今无人打破。
强悍的新秀查尔斯·奥克利在1985-86赛季加入公牛队，并迅速确立了球队篮板王的地位，他以场均8.6个篮板领先全队，3月15日对阵密尔沃基雄鹿队的比赛中，他抢下了18个进攻篮板，创下了球队纪录。直到这个赛季，公牛队还在寻找一位适合他们的主教练，赛季结束时，他们解雇了阿尔贝克。
1986-87赛季，公牛队迎来了另一位主教练道格·科林斯，公牛队将战绩提升至40胜42负，连续第三个赛季进入季后赛，但依然未能闯过首轮，被凯尔特人队再次淘汰。球队的战绩是球迷们第二关心的，他们最关注的是迈克尔·乔丹的表现。11月下旬和12月初，乔丹横行无忌，连续9场比赛得分40+。2月26日，对阵篮网队的比赛中砍下58分，其中罚球27投26中。3月4日，乔丹在对阵活塞队的比赛中再次砍下61分。仅仅一个月之后，4月16日，他在对阵老鹰队的比赛中再次砍下61分。本赛季结束，乔丹成为继1962-63赛季的威尔特·张伯伦之后，第二位单赛季得分3000+的球员。
乔丹本赛季场均得分37.1分，是职业生涯最高场均得分，本赛季他总共得到3041分，投篮命中1098次，罚球命中833次，抢断236次，凭借这样的表现，他首次入选联盟第一阵容。
1987-89 赛季：乔丹拥有强大的后援阵容
乔丹的伟大毋庸置疑，奥克利也相当出色，单赛季抢下1066个篮板，为联盟最多。但公牛队除了乔丹之外，仍然缺少一名得分点，而这个问题在1987年的选秀大会上得到了答案。公牛队总经理兼篮球事务副总裁杰里·卡劳斯用两个前十顺位选秀权为公牛队挑选了两名新秀——8号新秀奥登·波利尼斯和10号新秀霍勒斯·格兰特。前者被送到了西雅图超音速队，换来了5号新秀斯科特·皮蓬。这次选秀和交易对公牛队未来王朝的建立产生了巨大的影响。
随着格兰特和皮蓬的加盟，公牛队在乔丹的带领下开始展现天赋和能力，以50胜32负的战绩创造了1973-74赛季以来的最佳战绩。他们与亚特兰大老鹰队并列中区第二名，冠军是势不可挡的底特律活塞队。公牛队在季后赛中表现出色，首轮以4-1击败克利夫兰骑士队，但在东部半决赛中不敌底特律活塞队。
本赛季nba历史单赛季最糟糕的战绩纪录，奥克利与快船队的迈克尔·凯奇在篮板球上一直不分上下，直到常规赛最后一分钟。4月22日，奥克利在对阵骑士队的比赛中抢下35个篮板，仅次于1970年公牛队中锋汤姆·波尔温克尔的单场37个篮板。但两天后，他在对阵超音速队的比赛中抢下30个篮板，给奥克利造成了压力。最终，凯奇以场均13.03个篮板当选赛季篮板王，超过奥克利的13.00个篮板。不过，奥克利比凯奇少打了10场比赛，但仍以1066个篮板位居联盟第一。
乔丹包揽了本赛季几乎所有的奖项，凭借场均35.0分、3.16次抢断的出色表现，他不仅荣膺常规赛MVP，还斩获年度最佳防守球员、最佳阵容第一队、最佳防守第一队、全明星赛MVP、扣篮大赛MVP等荣誉。
虽然之前几个赛季公牛取得了不错的成绩，但显然他们已经没有了耐心。1988-89赛季，公牛队迎来了七位新面孔。克劳斯在1988年6月进行了几次大交易，先是把查尔斯·奥克利交易到尼克斯，换来身高2米16的比尔·卡特莱特，随后又从太阳队得到了三分射手克雷格·霍奇斯。人员变动导致公牛队本赛季常规赛只取得了47胜35负的战绩，但常规赛就是常规赛，只是季后赛的热身赛。
季后赛首轮，公牛3-2淘汰骑士，半决赛4-2击败尼克斯，球队历史上第三次打进东部决赛。东部决赛，公牛前三场2-1领先活塞，但活塞4-2连赢三场，挺进总决赛。乔丹连续第三个赛季位居得分榜首，场均32.5分。