1976-81赛季：1976赛季是ABA联盟并入NBA的赛季。公牛在新任主教练Ed Badger的率领下取得了20场的提高，达到了44胜38负。这个赛季开始之前，他们在ABA合并到NBA的分散选秀中得到了身高7英尺2英寸(2.18米)中锋阿阿提斯-吉尔默。效力肯塔基上校队5个伟大的赛季，吉尔默场均得到22.0分，之后开始了6个赛季的公牛生涯。吉尔默没能止住公牛的颓势，他们一度连败13场。但这一连串的失利被公牛在赛季下半段的出色表现所掩盖，他们在最后的24场比赛中取得了20场胜利，吉尔默、菜鸟斯科特-梅以及老将诺姆-范里尔都是首功之臣。赛季末段的狂奔帮助公牛杀入季后赛，但可惜还是未能再进一步。他们成为了新科冠军波特兰开拓者登顶的垫脚石，后者在中锋比尔-沃顿的带领下历史上首次夺冠。
1977-78赛季，公牛战绩略有下滑，尽管全名赛之前已经28胜23负，但整个赛季只有只有40胜42负，也缺席了季后赛。吉尔默代表公牛队参加了这一年的全明星赛，也是他在公牛队的第一次全明星之旅，6年公牛生涯他一共4次入选全明星阵容。本赛季他场均得到22.9分13.1次篮板球，投篮命中率55.9%位列联盟第三位。
接下来的赛季公牛每况愈下，战绩只有31胜51负。这个赛季公牛经历了两任主教练，拉里-科斯特洛赛季开始前接过了Ed-Badger的教鞭，但是他在开局20胜36负之后不得不下课，斯科蒂-罗伯特森接任，但剩余的赛季仅取得了11胜15负。吉尔默依旧是球队的头号得分手，场均23.7分外加12.7个篮板球，两项数据不仅是球队最高，而且在全联盟也排进了前十位。杰出的后卫Reggie Theus是公牛在1978年首轮选中的球员，入选了赛季最佳新秀阵容，开始了自己13个赛季的职业生涯。
1979-80赛季，公牛战绩更加糟糕，只有30胜52负。杰里-斯隆成为了球队的新任主教练，他在1976年退役之后一直担任球队的球探和助教。斯隆的首个赛季正好赶上吉尔默被腿伤困扰，前34场比赛没有参加，导致他670场连续出场纪录被自己终结。
1980-81赛季，公牛队被划分到了中部赛区，目的是为了新加盟的达拉斯小牛在中西赛区腾出位置。新赛区的环境对公牛十分有利，他们战绩一下反弹到45胜37负进排在密尔沃基雄鹿队60胜22负之后。公牛本赛季的胜率一直徘徊在50%左右，但赛季末段打出高潮，15场比赛取得了13胜2负的战绩。公牛自从1977年以来首次回到季后赛。公牛在首轮季后赛当中三战两胜制的赛制下，2-1击败纽约尼克斯，但东部半决赛当中被凯尔特人4-0横扫，后者夺得了赛季总冠军。
1981-84赛季：三年苦楚
1981年选秀大会上公牛选中了来自圣母大学身高6英尺9英寸(2.06米)的前锋奥兰多-沃尔里奇，尽管赛季开始前公牛看起来势头不错，但1981-82赛季依旧是个令人失望的赛季。12月2日公牛打了一场离奇的比赛，在与勇士的一场比赛中，尽管公牛命中率达到了70.5%，但依旧119-120不敌对手，这也打破了球队的历史纪录。在主教练杰里-斯隆带领下取得19胜32负之后，2月17日，公牛总经理罗德-索恩取代了斯隆接任球队主帅，剩余赛季公牛在索恩带领下取得了15胜15负，这个赛季以34胜48负结束。吉尔默依旧是球队的数据领袖，场均18.5分10.2篮板，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赛季：“飞人乔丹”
对这个萧条的赛季而言，第三位选秀权是个巨大的安慰。这一年选秀大会，休斯顿火箭队拥有状元签，他们选择了哈基姆-奥拉朱旺，一名未来统治中锋位置10年之久的大个子，也是历史上最具统治力的中锋之一。波特兰开拓者用榜眼签选了另外一名中锋萨姆-鲍威，但是他的职业生涯因为伤病不得不黯然谢幕。公牛队在第三顺位选中了北卡罗来纳大学的迈克尔-乔丹，一名身高6-6(1.98米)的后卫。
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年的NBA选秀大会上找到了答案。公牛总经理兼篮球事务副总裁杰里-卡劳斯用两个前十位选秀权为公牛摘下两名新秀——8号新秀奥登-波利尼斯和10号新秀霍勒斯-格兰特，前者被公牛打包选秀权送到了西雅图超音速换来了第五号新秀斯斯科特-皮蓬。这次选秀和交易对公牛未来王朝的建立影响巨大。
随着格兰特和皮蓬的加盟，公牛在乔丹的带领下开始展示他们的天赋与能力，以50胜32负的战绩创造了自1973-74赛季以来的最佳战绩。他们和亚特兰特老鹰队并列中部赛区第二名，冠军是肆虐的底特律活塞队。公牛季后赛小有表现，首轮4-1击败了克利夫兰骑士，但东部半决赛不敌底特律活塞队。
这个赛季，奥克利和洛杉矶快船队的迈克尔-凯奇在篮板球方面并驾齐驱，直到常规赛最后一刻在分出胜负。4月22日，奥克利在与骑士队的比赛中狂掳35个篮板，仅次于1970年公牛中锋汤姆-波尔温克勒的单场37个。但是两天之后，在对着西雅图超音速的比赛中抢到了30个篮板球，将压力甩给了奥克利。最终凯奇以场均13.03个领先奥克利的13.00个当选本赛季的篮板王。但是奥克利比凯奇少打了10场比赛的情况下，依旧以1066个篮板球位列联盟第一。
这个赛季乔丹获得了几乎所有的大奖。他以场均35.0分3.16次抢断的数据，不仅获得了常规赛MVP，而且还将年度最佳防守球员、最佳阵容第一队、最佳防守阵容第一队、全明星赛MVP，以及扣篮大赛冠军收入囊中。
尽管前几个赛季公牛取得了不错的战绩，但公牛显然没有耐心。1988-89赛季公牛出现了7张新面孔，克劳斯在1988年6月进行了几笔大交易，先是将查尔斯-奥克利交易到尼克斯换来身高2.16米的比尔-卡特莱特，再从太阳队得到三分投手克雷格-霍奇斯。人员的变动导致本赛季常规赛公牛仅取得了47胜35负的战绩，但常规赛是常规赛，只不过时季后赛的热身阶段。
季后赛首轮公牛3-2淘汰骑士队，半决赛4-2击败尼克斯，球队历史上第三次杀入分区决赛。东部决赛公牛在前三场2-1领先活塞队，但活塞连赢三场4-2晋级总决赛。乔丹连续第三个赛季领先得分榜，场均达到32.5分。