Posle objavljivanja singla, Bora Đođević zaključuje da mu je potrebna još jedna gitara da učvrsti zvuk i time ga definitivno odvoji od poređenja sa Bijelim dugmetom. Tada je Rajko u grupu doveo 19-godišnjeg gitaristu, Momčila Bajagića Bajagu, kojeg je poznavao iz sastava Glogov kolac. Prvi koncert u novoj postavi održali su 7. januara 1979. godine u Jarkovcu. U Domu omladine održali su 28. februara prvi beogradski koncert. Početkom marta su otišli da odsviraju dvadesetak koncerata po Makedoniji. Turneja je bila veliki uspeh, ali je u finansijskom pogledu bila neuspeh. Na koncertu u Dalovu, Miša je u zanosu promašio binu, pao i slomio nogu, pa ga je na koncertima po Sandžaku menjao Miroslav Cvetković (kasnije u Bajagi i instruktorima).
19. marta 1979, posle nekoliko svirki na kojim su promovisali pesme koje će se kasnije naći na debi albumu, objavljuju i drugi singl sa pesmama "Rokenrol za kućni savet" i "Valentino iz restorana". Pesmu "Valentino iz restorana" je komponovao Rajko na tekst Marine Tucaković. Pesmu su izveli i na Večeri slobodnih formi Festivala zabavne muzike u Opatiji. 1. septembra održana je i promocija debi ploče na Tašmajdanu. Želeći da napravi dobru zabavu za posetioce, Bora je koncert reklamirao parolom: "Riblja čorba neće da vam otima lovu - ulaz dva soma", što je u to vreme bila jako popularna cena. Kao predgrupa nastupile su grupe Bulevar u kome je tada pevao Dejan Cukić, a gitaru svirao Nele Stamatović i Formula 4 iz Sarajeva. Iznenađujuće je bilo da je publika znala sve pesme napamet, iako je album izašao tek deset dana posle koncerta.
1979, Bora i Rajko su otišli na služenje vojnog roka. Grupa nije odmah uzela predah, pošto su 28. novembra 1979. godine svirali na maratonskom koncertu u Sarajevu. Nastupali su bez Bore, Rajko je svirao u uniformi, a Miša je, budući da nije znao sve tekstove, inicijativu prepuštao publici. Ubrzo je i on otišao u vojsku.
Debi album "Kost u grlu", snimljen je 1979. godine. i tada je Bajaga prvi put sa njima radio u studiju. Doduše, zbog efikasnog korišćenja vremena, njegove deonice je odsvirao Rajko Kojić. Ploču je producirao Enco Lesić, a pored Bore, kao autori se potpisuju Miša, Rajko i Nenad Božić iz Suncokreta koji je bio koator muzike za pesmu "Mirno spavaj". Sve pesme na ploči nastale su kao plod Borinog novog interesovanja za teme koje obrađuju svakodnevnicu, a neuvijen jezik je u startu izazvao probleme. Tako je u pesmi "Mirno spavaj", sporan stih "popij svoje sedative" jer asocira na drogu, zbog čega je jedan čitav deo tiraža morao biti povučen. Prvih stotinak prodatih primeraka ploče sa originalnim tekstom dnas imaju status rariteta. Bora je preventivno promenio ime pesme "Još jedan usran dan" u "Još jedan šugav dan". Osim nje, na albumu su se našle i pesme "Ostani đubre do kraja", "Zvezda potkrovlja i suterena", "Egoista", "Pozajmila je pare, poludela je skroz, kupila je kartu i sela na voz" itd.
Konačni tiraž ploče Kost u grlu se zaustavio na oko 120.000 prodatih kopija. U muzičkim novinama Boru su proglašavali za rok ličnost godine, a njihov hard rok zvuk sa bluz elementima nije smetao, iako su pank i novi talas već počeli da postižu popularnost. Krajem jula 1980. godine Bora se, zahvaljujući primernom ponašanju u vojsci, pojavio u Beogradu na nagradnom odsustvu. Uz Rajka Kojića koji je pobegao iz sarajevske kasarne, Bajagu i Vicka za jednu noć su snimili pesmu "Nazad u veliki prljavi grad". Kako Miša nije dobio dozvolu vojnih vlasti da dođe, Bajaga je snimio i bas deonice. Po povratku u kasarnu, Rajko je dobio 15 dana zatvora, jer je njegov pretpostavljeni video Rajkovu sliku u novinama. Singl sa pesmom "Nazad u veliki prljavi grad" pojavio se 1. septembra 1980. godine. Na B-strani se našla necenzurisana verzija pesme "Mirno spavaj" koja najednom više nikome nije smetala.
Uoči Nove godine iz vojske je stigao i Rajko, pa kompletirani sviraju 31. decembra i 1. janura nove 1981. godine sa Atomskim skloništem u hali Pionir na koncertima pod nazivom "Atomska čorba".
Po povratku iz armije, grupa ulazi u studio Ence Lesića i do polovine februara 1981. grupa je snimala album "Pokvarena mašta i prljave strasti", za koju je Bora iz vojske slao tekstove za neke pesme, dok bi ga u povratku čekale gotove pesme, za koje je uglavnom bio zaslužan Bajaga. Od ostalih pesama sa ovog albuma vredne pomena su: "Ostaću slobodan", "Lak muškarac", "Neke su žene pratile vojnike". Bajagina stvar "Dva dinara, druže" je bila prve od tri stvari Riblje čorbe koja je postala hit godine na Hitu 202. Album je krajem 1981. dostigao tiraž od 200.000 primeraka. Zvanično se pojavio u prodavnicama 23. februara, a nedelju dana pre toga Riblja čorba je trijumfovala na zagrebačkim koncertima u okviru akcije "Pozdrav iz Beograda". Planirano je da se na omotu albuma pojavi osamdesetogodišnja gospođa, ali se otprilike u to vreme pojavio album Bijelog dugmeta "Doživjeti stotu" sa sličnim rešenjem, pa se na kraju na omotu našao književnik Miloš Jovančević. Tokom dva koncerta u novobeogradskoj Hali sportova u kojoj se okupilo blizu 5.000 posetilaca po večeri. Ovaj nastupje bio uvod u uspehe koje je grupa postigla tokom turneje po Jugoslaviji kada su obišli 59 gradova. Krajem juna bili su zvezde večeri na "Vjesnikovom" koncertu u Zagrebu na kome su se okupile vodeće domaće grupe. Miša zbog ženidbe nije mogao da svira, pa ga je opet menjao Miroslav Cvetković.
Riblja čorba već tada izvodi neke stvari sa novog albuma. Inače, koncerti su praćeni brojnim incidentima uzrokovanih najezdom publike i lošim obezbeđenjem. Prvi znak budućih nevolja je tzv. "koncert za polomljena rebra" 10. septembra 1981. u Rokoteci na Kalemegdanu gde je ograda probijena, pa samo čudom niko nije poginuo, mada je bilo mnogo slučajeva za urgentni centar i stotine izgubljenih cipela. Uprkos povredama, koncert je u novinama dobio dobre kritike, a te večeri su odsvirali i deo novih pesama sa gostom iz Engleske, basistom Džonom Mekojem.
U novembru je izašao i treći album "Mrtva priroda", koju je producirao Mekoj. Bajaga je sam napisao "Ja sam se ložio na tebe", dok su ostale udarne stvari bile produkt Borinih tekstova i muzike od strane svih. Na albumu su se još pojavile i "Ne veruj ženi koja puši Drinu bez filtera", "Odlazak u grad", "Na zapadu ništa novo", "Pekar, lekar, apotekar", "Neću da ispadnem životinja", "Volim, volim žene". Album se prodaje u rekordnih 500.000 primeraka i Riblja čorba se probija na sam vrh jugoslovenske muzičke scene.
Grupa je započinje turneju, koja je, ispostaviće se, malo nezgodno nazvana: "Ko preživi - pričaće". Naime, na koncertu u zagrebačkoj Ledenoj dvorani 8. februara 1982. se pojavilo 15.000 mladih, a pošto su samo dveja vrata bila otvorena, u gužvi je izgažena 14-godišnja Zagrepčanka Željka Marković, koja je preminula od povreda. To je Bori stvorilo dodatne nevolje koje su već bile velike.
Početkom februara u "Ilustrovanoj politici" objavljeno je pismo u kom je pisano na temu političke podobnosti Riblje čorbe. To je bilo dovoljo da SUBNOR skopske opštine Karpoš podnese zahtev da se ploča zabrani zbog stihova "Za ideale ginu budale" i "Kreteni dižu bune i ginu" iz pesme "Na Zapadu ništa novo". Odmah posle njih, tom zahtevu se pridružuju SUBNOR Sarajeva i SUBNOR Bezdana, ali i Savez socijalističke omladine Bosne i Hercegovine. Afera poprima velike razmere po medijima, pa Riblja čorba je bila prisiljena da u Čelju prvi put u karijeri prekine svoj koncert, jer su dežurni vatrogasci bili previše agresivni prema publici. Koncert u Sarajevu mogao je da bude održan tek kada je Bora napisao obrazloženje za tekstove svih pesama koje će izvoditi i potpisao da će "Na Zapadu ništa novo" otpevati na sopstvenu odgovornost. U Tuzli nisu mogli da sviraju jer, kako je bilo izjavljeno, "organizator ne može da obezbedi red i mir tokom koncerta grupe čije ponašanje nije u skladu sa socijalističkim moralom". Čitava stvar se smirila kada je grupu odbranio tadašnji predsednik boračke organizacije.
Promotivnu turneju povodom ploče "Mrtva priroda", Riblja čorba je završila svirajući četiri večeri uzastopno, polovinom aprila 1982. godine u beogradskoj hali Pionir. Koncerti su održani sa mesec dana zakašnjenja, jer su organizatori otezali zbog slučaja u Zagrebu, plašeći se da li će moći da ponude adekvatno obezbeđenje. Razloga za strah nije bilo jer su prve večeri svirali u polupraznom Pioniru, što je bilo veliko iznenađenje. Ipak, druge dve večeri su bile popunjene na pravi način, a na nastupu od 11. aprila snimljen je njihov koncertni album "U ime naroda". Ploča je dobila naziv po uzoru na početnu repliku kojom se izriče presuda u sudu i time se jasno aludiralo na Borine političke probleme. Tokom četiri dana Čorbu je "gledalo 21.000 ljudi zajedno sa mnogobrojnim redarima i milicionerima". Političko smirivanje oko Čorbe rezultiralo je neobičnom odlukom. Na Dan mladosti i na rođendan maršala Tita, 25. maja 1982. godine, dobili su Majsku nagradu Gradskog komiteta Saveza socijalističke omladine uz obrazloženje da "grupa peva o životu i problemima mladih i da je postala unekoliko simbol velikog dela omladine".
Ploča "U ime naroda" izlazi par meseci kasnije i kao i sve prethodne prolazi odlično, postigavši tiraž 12.0000 i postao najprodavaniji koncertni album u dotadašnjoj jugoslovenskoj rok istoriji. Nekoliko dana kasnije Riblja čorba je, uz druge domaće grupe svirala na Trgu Marksa i Engelsa na koncertu povodom solidarnosti sa borbom naroda Palestine. U toku godine dolazi do prvih većih nesuglasica u bendu. Bora želi još jedan album do kraja godine, dok Bajaga smatra da je potrebna pauza.
Ipak, Borina je zadnja, i u jesen izlazi i peti album "Buvlja pijaca", koji je već u sebi imao dosta komercijalnog zvuka, ali i slabijih tekstova. Ploču je opet producirao Džon Mekoj, a miks je urađen u Londonu. Uz Čorbu je na snimanju učestvovao Kornelije Kovač koji je svirao klavijature, dok su se u nekim pesmama pojavili gudači i duvačka linija, tako da je ploča u sebi nosila i neke od elemenata akustičnog zvuka. Bora je uradio tekstove za sve pesme, sem za "Bejbi, bejbi don't vona kraj" koja je kompletno Bajagina. Tu pesmu je prvobitno trebalo da peva Slađana Milošević na svojoj ploči, ali je Bora insistirao da ostane Čorbi. Kao autori muzike na ostatku materijala potpisali su se Miša, Rajko i Vicko. Bora je definitivno promenio tematiku i na albumu su se našle pesme sa "društvenom" porukom poput "Slušaj, sine", "Ja ratujem sam", "Pravila", "Kad ti se na glavu sruči čitav svet", "Kako je lepo biti glup" (inspirisana Borinim boravkom u JNA). Pesme s albuma se pojavljuju i kao nekakav "saundtrek" za komediju Tesna koža. Ipak, i pored prodatih 300.000 ploča, ovaj album se smatra početkom pada Riblje čorbe. Grupa je na turneju krenula dve nedelje po objavljivanju ploče i suočila se sa oslabljenim interesovanjem publike.
Na osnovu glasova čitateljki Bazara, Bora je izabran za idealnog muškarca, na šta je on odgovorio pesmicom "Domaćice, skinite gaćice, ja volim vaše flanelske spavaćice".
Veliku turneju su završili početkom aprila 1983. godine ambicioznim koncertom na Sajmištu za koji je Bora želeo da postane njegova Hajdučka česma. Ideja za Sajmište je bila Borina, budući da je bio sentimentalno vezan za taj prostor jer ga je kao dečaka na jednu od čuvenih gitarijada koje su se tu održavale odveo Petar Popović.
U želji da obnovi taj prostor, Bora je skoro sam sa Mišom Aleksićem organizovao koncert. Potrudili su se da naprave najveću binu koja je do tada viđena u Jugoslaviji, a nju je pratilo adekvatno kvalitetno svetlo i ozvučenje. Bora je sa Markom Jankovićem i Zoranom Modlijem snimio radijske reklame. U zalaganju za koncert išao je tako daleko da je sa Modlijem iz aviona bacao letke iznad Novog Sada, Zrenjanina, Šapca, Pančeva i Beograda. Koncert je išao pod imenom "Hleba i igara", a kao predgrupe su nastupali D'Bojs i Siluete, u kojima je tada gitaru svirao mladi Nikola Čuturilo. Za održavanje reda bilo je angažovano 170 milicionera i 340 redara. Bora je očekivao veliku gužvu, pa se čak sa prijateljima opkladio da će se, ako ne proda 10.000 karata, ošišati do glave. Kako je prodato samo 8.000, Bora se zaista posle svirke obrijao do glave. A tome je prethodilo još jedno ritualno šišanje, jer se te večeri grupa oprostila od Vicka Milatovića koji je odlazio u vojsku, pa su ga odmah na bini ošišali i upristojili za armiju. Umesto njega, na bubnjarsku stolicu seo je Vlajko Golubović, čovek koji je pre toga bio u sastavima Tilt i Suncokret, a kasnije i u Bajagi i Instruktorima.
Pauzu u radu grupe prvi je iskoristio Rajko Kojić i objavio mini album "Ne budi me bez razloga" (PGP RTB 1983). Rajko je napisao muziku, a Bora i Bajaga tekstove. Na ploči su svirali klavijaturista Laza Ristovski, basista Neša Japanac i Vlajko Golubović, a Bora je otpevao tri svoja i jedan Bajagin tekst . Krajem iste godine, Bajaga odlučuje da snimi svoj album "Pozitivna geografija", posle niza stvari urađenih za druge (Bulevar, Zdravko Čolić).
1984. izlazi "Pozitivna geografija" i Bajaga postaje hit broj 1 u zemlji. Ipak, tvrdi da ostaje veran Ribljoj čorbi, što pokazuje i ulazak u studio i album "Večeras vas zabavljaju muzičari koji piju". Kako u PGP RTB-u nisu želeli da Čorbi finansiraju snimanje u Londonu, prešli su u zagrebački Jugoton. Ploču je sa članovima grupe producirao Kornelije Kovač u Ljubljani, a miks je urađen u Londonu. Odmah po objavljivanju, 1984. godine, republička cenzura je tri pesme proglasila moralno nepodobnim, pa je ploča dobila etiketu šund proizvoda i samim tim veću cenu u prodaji. Album izlazi u proleće i po mnogima je jedan od najboljih. Kao prvo, ritam je drugačiji zbog odsustva Vicka za bubnjevima, a muzika pretežno Bajagina, što se pokazalo kao dobitna kombinacija. Bajaga je napisao muziku za pet pesama, uključujući dve kompletno njegove "Kad hodaš" i "Večeras vas zabavljaju muzičari koji piju". Probleme su zbog tekstova stvorile "Mangupi vam kvare dete" i "Besni psi" u kojoj, pored ostalog, Bora peva: "Grčki šverceri, arapski studenti, negativni elementi, maloletni delikventi i besni psi", što je izazvalo internacionalne potrese. Ambasade tri arapske zemlje, pa čak i afričke države Zair žalile su se zato što je Bora izjednačio arapske studente i besne pse. Onda je Republičko ministarstvo kulture naručilo stručnu analizu pesme, a pred Čorbin beogradski koncert stigao je zahtev iz SIP-a da se pesma ne izvodi. Turneja, i pored sjajnog albuma, prolazi prilično loše. Ploča je prodata u, za tu godinu, rekordnih 120.000 primereka, i pored toga što je i zvanično bila proglašena "šundom".
