Группа была создана в 1986 году Эриком Стефани (Eric Stefani) и Джоном Спенсом (John Spence), и изначально называлась Apple Core. Эрик выступил клавишником, а Джон — вокалистом. Также, в качестве вокалистки второго плана Стефани пригласил свою сестру Гвен (Gwen Stefani). Несколько месяцев группа искала музыкантов, а затем репетировала. Вскоре коллектив стал играть на вечеринках, исполняя хиты разных групп и некоторое количество своих песен.

Первым присоединившимся к группе музыкантом стал басист Тони Кэнел (Tony Kanal). Это произошло в марте 1987 г. после одного из концертов. Ранее Тони играл джаз и был хорошо образован в музыкальном плане, а так как он обладал ещё и администраторскими способностями, то взял на себя обязанности менеджера.

Неожиданностью для всех стало самоубийство вокалиста группы 21 декабря 1987 года. Джон Спенс застрелился в городском парке. «No Doubt» («несомненно», «нет сомнений») — было его любимым выражением. Это событие потрясло всех участников группы, а всю ответственность за вокал взяла на себя Гвен. Весной 1989 года в группу вступает гитарист Том Дюмонт (Tom Dumont), добавив тяжести звучанию, а место за барабанами летом 1989 г. занимает Эдриан Янг (Adrian Young), солгав группе, что имеет большой стаж (на самом деле он играл всего год).

Контракт на запись дебютного альбома группа подписала в августе 1991 года с компанией Interscope Records. В то же время все участники No Doubt продолжают учиться в колледжах и работать: Гвен и Тони — продавцами, Эдриан — официантом в закусочной, Том специализировался в работе с музыкальным оборудованием.

Новый альбом, названный просто «No Doubt», появился на прилавках магазинов в марте 1992-го. Продажа шла вяло, а местная радиостанция «KROQ» отказалась от ротации песен в своём эфире. Коллектив начинает двухнедельное турне по западу США в поддержку своего альбома. Вся дорожная команда (пять членов группы, духовая секция из 3-х человек, техник, дорожный менеджер/звукооператор) и аппаратура помещаются в двух небольших фургонах. Летом 1992 года снимается первый клип группы на песню «Trapped In A Box». Вскоре из-за неудовлетворительных продаж Interscope отказывается продолжать сотрудничество с No Doubt, но, несмотря на это, музыканты решают выпустить следующий альбом самостоятельно. Запись происходила в трех разных местах, в том числе в гараже дома Стефани на Бикон Стрит (Beacon Street). В честь этой улицы альбом и получил своё название — «The Beacon Street Collection». Диск вышел в середине 1995 г., но по причине отсутствия контракта и соответствующей поддержки не появился в крупных магазинах и чартах, а распространялся на концертах и через местные магазины в городках, где проходили гастроли. Interscope, поменяв своё решение, предложила группе записать несколько демозаписей, а в дальнейшем и альбом. No Doubt начинает трудиться над новыми записями, но, незадолго до завершения работы, группу оставляет Эрик Стефани, продолжив свою творческую деятельность в качестве художника-мультипликатора в сериале «The Simpsons».

Третий альбом под названием «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 отправляются в следующее большое турне по самым крупным городам, играя в самых больших залах.

В январе 1997 г. No Doubt была выдвинута на American Music Awards в категории «Favourite New Artist pop/rock». Для молодых музыкантов это было большим достижением, несмотря на то, что премию они не получили. Через месяц последовало представление на Grammy Awards в категориях «Best Rock Album» и «Best New Album», но снова ни одна награда им не достается. 4 сентября 1997 г. видеоклип на песню «Don’t Speak» побеждает в номинации «Best Group Video» на вручении премий MTV Video Music Awards. Также увеличиваются объёмы продаж первого альбома «No Doubt», и 21 октября 1997 года Interscope Records вновь выпускает «The Beacon Street Collection» образца 1995 года. В ноябре выпускается первое концертное видео «Live In The Tragic Kingdom» — полуторачасовое выступление в зале «The Arrowhead», Анахайм.

В начале 1998 года после практически беспрерывной серии концертов группа приступает к работе над следующим студийным альбомом. Это заняло длительное время, в течение которого музыканты участвуют в церемониях награждений, записывают песню «New» для саундтрека к фильму «Go», а Гвен подпевает разным исполнителям и делает кавер-версии.

Ради турне по западу США No Doubt прерывает студийную сессию в сентябре 1999 года, после чего дописывают несколько треков в студии.

1 января 2000 года, сразу же после боя Кремлёвских Курантов, музыканты исполняют свою новую песню «Ex-Girlfriend» и кавер группы R.E.M. «It’s the End of the World as We Know It» в прямом эфире MTV.

Тем временем начинается первый в жизни группы спланированный промоушен нового альбома. В ротацию на радио поступает песня «Ex-Girlfriend», а чуть позже на MTV заявляется клип на эту композицию, премьера которого проходит 7 Февраля. Вслед за этим группа появляется в нескольких телешоу на MTV, NBC и VH1.

11 апреля 2000 г. под названием «Return Of Saturn» выходит новый альбом музыкантов, через неделю на MTV появляется следующий ролик на песню «Simple Kind Of Life».

No Doubt отправляются в двухмесячное турне по Штатам в поддержку альбома, который в Июне становится «платиновым». После американского тура в августе снимается видео на песню «Bathwater», а в Сентябре группа едет в Европу, Японию и Австралию.

Далее следует выдвижение No Doubt на VH1/Vogue Fashion Awards:
Видео «Ex-Girlfriend», как Most Stylish Video (самое стильное видео);
Видео «Simple Kind Of Life», как Most Visionary Video (самое зрелищное видео);
Most Stylish Band (самая стильная группа).

Группа побеждает в первой номинации. В это же время (октябрь 2000 г.) появляется информация о том, что в конце года No Doubt могут приступить к работе над следующим альбомом, хотя вскоре после выхода «Return Of Saturn» группа заявила, что не планирует выпускать ещё один альбом. Это было воспринято чуть ли не как заявление о скором распаде коллектива.