Historia 1987–1994 thumb|Jens Kidman podczas Getaway Rock Festival w 2012 r. Zespół powstał w 1987 roku z inicjatywy wokalisty i gitarzysty Jensa Kidmana. Nazwę „Meshuggah” zaczerpnął z języka jidysz, w którym słowo to znaczy „szalony”. Po nagraniu kilku materiałów demo Kidman opuścił zespół. Wkrótce potem założył grupę o nazwie Calipash; w jej skład weszli późniejsi członkowie Meshuggah: gitarzysta Fredrik Thordendal, basista Peter Nordin i perkusista Niclas Lundgren. Kiedy Calipash przestał istnieć, muzycy zdecydowali się wykorzystać nazwę Meshuggah na potrzeby nowego zespołu. W początkowym okresie twórczość grupy była inspirowana dokonaniami grupy Metallica.
W 1989 roku ukazał się pierwszy minialbum zespołu, pt. Meshuggah, znany również pod nazwą Psykisk Testbild, w nakładzie 1000 egzemplarzy. Tego samego roku zespół wydał własnym nakładem demo pt. Ejaculation of Salvation. W 1990 roku zespół opuścił perkusista Niklas Lundgren, którego zastąpił Tomas Haake. Wkrótce potem zespół podpisał kontrakt płytowy z Nuclear Blast Records. W 1991 roku ukazał się debiutancki album Meshuggah pt. Contradictions Collapse, który zdobył pozytywne recenzje, lecz nie odniósł sukcesu komercyjnego. Niedługo później Kidman zdecydował się skupić na roli wokalisty i przestał grać na gitarze.