Сначала Primus назывался «Primate», и был образован в El Sobrante (Калифорния) в середине 1980-х Лесом Клэйпулом и гитаристом Todd Huth. Они использовали драм-машину, но в записи демо-кассеты принял участие ударник Perm Parker. В ранние годы в группе сменилось множество ударников. Primus открывали концерты таких трэшевых коллективов, как Testament и Exodus.

В 1989 году все, кроме Клейпула, покидают группу, и он собирает новый состав с Larry «Ler» LaLonde (бывшим гитаристом группы Possessed и некогда учеником Джо Сатриани) и эклетичным ударнкиом Tim «Herb» Alexander.

Дебютный альбом «Suck on This» вышел в 1989 году, и является записью с двух концертов в Беркли. Альбом финансировался отцом Леса Клейпула.

Первый студийным альбом «Frizzle Fry» вышел в 1990 году, и в том же году Primus подписали контракт с лейблом Interscope Records.

При поддержке мейджор-лейбла следующий альбом «Sailing the Seas of Cheese» (1991) стал «золотым». Клипы группы появились на MTV. Альбом 1993 года «Pork Soda» достиг 7 места в чартах Top 10 журнала «Billboard Magazine».

В 1990-х годах музыкальная карьера Primus была весьма успешной. Группа возглавляла альтернативный фестиваль Lollapalooza в 1993 году, появилась в телешоу Дэвида Леттермана и Конана О’Брайена в 1995, и даже выступила на фестивале «Woodstock '94». На альбоме 1995 года «Tales from the Punchbowl» присутствует песня «Wynona’s Big Brown Beaver» — самый успешный сингл группы на сей день (2006), номинировавшийся на премию Грэмми.

В 1996 году Primus написали музыку к мультсериалу «South Park» — его создатели оказались большими фэнами группы ; чуть позже они записали песню «Mephisto And Kevin» для связанного с сериалом альбом «Chef Aid: The South Park Album». Кроме того, группа создателей «South Park» DVDA записала кавер-версию песни Primus «Sgt. Baker».

В 2000 году Primus совместно с Оззи Озборном (вокал) записали кавер-версию на композицию Black Sabbath «N.I.B.». Она была выпущена синглом, а также на альбоме-трибьюте «Nativity in Black II: A Tribute to Black Sabbath» и на бокс-сете Озборна «Prince of Darkness». Сингл поднялся на второе место в хит-параде «Billboard Modern Rock tracks».

В 2000 году Лес Клэйпул стал активно участвовать в других своих проектах («Colonel Les Claypool’s Fearless Flying Frog Brigade», «Oysterhead»), и группа практически прекратила активность. Только в 2003 году Primus снова воссоединились для записи DVD/EP «Animals Should Not Try to Act Like People», после чего состоялись концертные турне Primus и нерегулярные выступления на различных фестивалях. Некоторые концерты Primus, начиная с 2003 года, состоят из двух отделений, второе из которых включало в себя полностью материал одного из первых альбомов. В 2003 году это был альбом «Sailing the Seas of Cheese» (1991), в 2004 «Frizzle Fry» (1990).