Назва "Motordog" також було відзначити і, нарешті, з подачі одного з друзів Сіккса зупинилися на "Brides of Destruction". Гамільтон пробув в команді недовго і ретирувався, поступившись місцем колишньому учасникові "Motley Crue" Джону Кораби.
Оновлений склад зробив пробні записи, а в листопаді втік і Колс. Посадивши за ударні Скотта Куган, "деструктивні нареченої" продовжили писати матеріал, а в грудні відіграли кілька концертів на розігріві у "Mudvayne" і "Taproot".
Навесні 2003-го Куган виїхав на гастролі з "Otep", Кораби взагалі склав свої повноваження, і наступні кілька місяців "Brides of Destruction" не діяли, ліниво пережовуючи можливості контракту з яким-небудь лейблом. Нарешті, колектив зробив вибір на користь "Sanctuary Records" і зайнявся підготовкою дебютного альбому. "Here Come The Brides", що представляв собою суміш добротного хард-року, глем-металу і пост-гранжу, вийшов у 2004 році. Диск пробився в гарячу сотню "Billboard" (92-е місце), а його тираж в перший тиждень склав 13000 копій. Особливу увагу привернув сингл "Shut the Fuck Up", спрямований проти політиків, які обговорюють методи боротьби з терором.
Втім, через ненормативної лексики в ефір пішла відредагована версія цієї пісні, і тому в чарти композиція не потрапила. На підтримку альбому "Brides of Destruction" провели невелике турне, а в 2005-м Ніккі Сіккс залишив проект, возз'єднавшись зі своїми колегами з "Motley Crue".
Вакансію басиста зайняв Скотт Соррі з "Amen" (спочатку планувалося взяти Стіва Бруно), а другим гітаристом "BoD" став Джинджер з "The Wildhearts". Оновлений склад приступив до підготовки другого альбому, проте не пройшло і місяця, як Джинджер залишив свій пост. Як би там не було, але сесії довели до кінця, і у вересні 2005-го перші екземпляри "Runaway Brides" лягли на прилавки музичних магазинів. Диск був виданий уже на іншому лейблі, "Shrapnel Records". Коли команда вирушила на гастролі до Європи, в її складі вже не значилося Скотта Соррі. Частина концертів за нього відіграв Джеремі Ганз, трудився раніше в "Brides of Destruction" як гітарний технік, а на інших сетах басуху терзав Деззл Ребел.
На початку 2006-го лідер "деструктивних наречених" Трейсі спантеличив всіх своїм переходом в "Quiet Riot". І хоча в цій групі пробув він не більше місяця, в свій попередній проект гітарист так і не повернувся, а над майбутнім "BoD" був поставлений жирний знак питання.