Группа была создана в 1986 году Эриком Стефани и Джоном Спенсом и изначально называлась Apple Core («сердцевина яблока»). Эрик выступил клавишником, а Джон — вокалистом. В качестве вокалистки второго плана Стефани пригласил свою сестру Гвен. Несколько месяцев группа искала музыкантов, а затем репетировала. Вскоре коллектив стал играть на вечеринках, исполняя хиты разных групп и некоторое количество своих песен.
Первым присоединившимся к группе музыкантом стал басист Тони Канэл. Это произошло в марте 1987 г. после одного из концертов. Ранее Тони играл джаз и был хорошо образован в музыкальном плане, а так как он обладал ещё и администраторскими способностями, то взял на себя обязанности менеджера.
Неожиданностью для всех стало самоубийство вокалиста группы 21 декабря 1987 года. Джон Спенс застрелился в городском парке. Его любимым выражением было «no doubt» («несомненно», «без сомнений»). Это событие потрясло всех участников группы, а всю ответственность за вокал взяла на себя Гвен. Весной 1989 года в группу вступает гитарист Том Дюмон, добавив тяжести звучанию, а место за барабанами летом 1989 г. занимает Эдриан Янг, солгав группе, что имеет большой стаж (на самом деле он играл всего год).
Контракт на запись дебютного альбома группа подписала в августе 1991 года с компанией Interscope Records. В то же время все участники No Doubt продолжают учиться в колледжах и работать: Гвен и Тони — продавцами, Эдриан — официантом в закусочной, Том специализировался в работе с музыкальным оборудованием.
Новый альбом, названный просто No Doubt, появился на прилавках магазинов в марте 1992 года. Продажа шла вяло, а местная радиостанция KROQ отказалась от ротации песен в своём эфире. Коллектив начинает двухнедельное турне по западу США в поддержку своего альбома. Вся дорожная команда (пять членов группы, духовая секция из трёх человек, техник, дорожный менеджер/звукооператор) и аппаратура помещаются в двух небольших фургонах. Летом 1992 года снимается первый клип группы на песню «Trapped in a Box». Вскоре из-за неудовлетворительных продаж Interscope отказывается продолжать сотрудничество с No Doubt, но, несмотря на это, музыканты решают выпустить следующий альбом самостоятельно. Запись происходила в трёх разных местах, в том числе в гараже дома Стефани на Бикон Стрит (Beacon Street). В честь этой улицы альбом и получил своё название — The Beacon Street Collection. Диск вышел в середине 1995 г., но по причине отсутствия контракта и соответствующей поддержки не появился в крупных магазинах и чартах, а распространялся на концертах и через местные магазины в городках, где проходили гастроли. Interscope, поменяв своё решение, предложила группе записать несколько демозаписей, а в дальнейшем и альбом. No Doubt начинает трудиться над новыми записями, но незадолго до завершения работы группу оставляет Эрик Стефани, продолжив свою творческую деятельность в качестве художника-мультипликатора в сериале «Симпсоны».
Третий альбом под названием Tragic Kingdom выходит в октябре 1995 года. Запись происходила частями в 11 разных студиях и объединяла такие стили как ска, новая волна, панк и поп. Первоначально этот диск также не вызвал большого интереса, но спустя несколько месяцев, в январе 1996 г., альбом дебютирует в Billboard Top 200 под № 175, а песня «Just a Girl» занимает 10-ю позицию. Благодаря этому No Doubt пригласили в популярное вечернее телешоу, где музыканты исполнили песню в прямом эфире. Ещё одна композиция — «Spiderwebs» — в июне 1996 г. становится № 5 в том же Billboard, после чего начинается первое большое турне по Европе, а затем и по Австралии, Новой Зеландии, Индонезии и Японии. После семи лет работы No Doubt наконец становятся всемирно известными и выходят на большую сцену уже в качестве хедлайнеров. В июле 1996 г. альбом Tragic Kingdom стал платиновым, а в августе — дважды платиновым.
В ноябре 1996 года баллада «Don’t Speak» достигает 2-й и 1-й позиций в разных категориях Billboard. На этой же неделе продается около 230 000 копий альбома, а на следующей, рождественской, — более 500 000. Объём общей продажи составляет к концу 1996 года 6 млн экземпляров. Альбом останется № 1 ещё 9 недель и 36 недель в десятке лучших. На волне этого успеха No Doubt отправляются в следующее большое турне по самым крупным городам, играя в самых больших залах.