Kapela nejprve vydala singl, na němž byly dvě písničky Quiet in Heaven a Song of Liberty, a vyzkoušela různé zpěváky – mezi nimi například i zpěvačku Courtney Love. Až v roce 1983 se součástí stálé hudební sestavy stal Chuck Mosely.

V témž roce nahradil Marka Bowena kytarista Jim Martin. V následujícím roce skupina vydala své první demo, které obsahovalo čtyři skladby a stalo se základním kamenem jejich debutového alba s názvem We Care A Lot, jež vyšlo v roce 1985. O dva roky později, po vydání druhého alba pojmenovaného Introduce Yourself, skupina vyrazila na úspěšné evropské turné.

V roce 1988 byl kvůli svému opilství a zhoršující se kvalitě zpěvu z kapely vyhozen excentrický zpěvák Chuck Mosely. V kapele za něj zaskočil devatenáctiletý Mike Patton, kterého ve středoškolské kapele Mr. Bungle objevil Jim Martin. Začátkem roku 1989 se skupina na šest měsíců zavřela do nahrávacího studia. Zde vytvořila desku, která se řadí k nejdůležitějším hudebním počinům v posledních pětadvaceti letech. Album The Real Thing bylo totiž předznamenáním toho, kterým směrem se bude moderní rocková hudba ubírat. Ačkoli se zpočátku nezdálo, že deska skupině přinese nějakou slávu, rok po vydání alba už se Faith No More mohli radovat z pozornosti hudebních kritiků i posluchačů. Úspěch jim přinesla především skladba Epic, za kterou byli nominováni na cenu Grammy. Na konci roku 1989 se album stalo platinovým.

S prací na novém albu nazvaném Angel Dust přišly také první problémy. Kytaristovi Jimu Martinovi se totiž nelíbilo, kam hudební tvorba kapely směřuje. Ačkoli mělo album velký úspěch, žádná skladba už se do mozku posluchačů nevryla tolik jako píseň Episc. Neshody s Martinem vyvrcholily po turné v roce 1993 a v listopadu téhož roku z kapely odešel. Nahradil ho kytarista Trey Spruance, s nímž skupina v roce 1995 nahrála další album King for a Day… Fool for a Lifetime! Ani ten však v kapele dlouho nevydržel a ještě předtím, než Faith No More vyrazili na turné, nahradil ho Dean Menta. Deska se v australské hitparádě vyhoupla na první místo a o popularitu neměla nouzi ani v evropských zemích. Jedinou zemí, která o album nejevila sebemenší zájem, byly Spojené státy.

V následujících dvou letech se členové kapely soustředili především na své vlastní projekty – například Mike Bordin vyrazil na turné s Ozzy Osbournem a Mike Patton koncertoval se skupinou Mr. Bungle. Ve skupině navíc došlo k další výměně kytaristy. Deana Mentu nahradil Jon Hudson, bývalý člen skupiny Systems Collapse. Poslední studiové album skupiny, na jehož obale byla podobizna Tomáše Garrigua Masaryka, vyšlo v červnu 1997 pod názvem Album of the Year a bylo úspěšné jak v Evropě a Austrálii, tak i ve Spojených státech.

V dubnu 1998 vydal Billy Gould toto prohlášení: „Po patnácti dlouhých a úspěšných letech se Faith No More rozhodli, že učiní konec spekulacím o jejich rozpadu tím, že se rozpadnou. Je to společné rozhodnutí všech členů, a proto už není žádný důvod pokračovat dalším albem. Dalším důvodem je to, že každý bude mít mnohem víc času na své individuální projekty. Nakonec to nejdůležitější, kapela chce poděkovat všem fanouškům a asociacím, které byli kapele Faith No More po dobu jejího trvání nakloněni.“