У 1970-му Біл разом з однодумцями зібрав близьку до госпел групу, з якою він виступав до середини 1971 року, після чого зайнявся самостійної кар'єрою. Записана за допомогою Річарда Брауна (фісгармонія, фортепіано, ударні), басистів Гарета Ейлліджа і Леона Артурса платівка "Northern Dream", принесла Біллу Нельсону репутацію самобутнього виконавця. Один з її 250 примірників дійшов до диск-жокея Джона Піла, вперше транслював запису Нельсона в радіоефірі. Він-то і допоміг привернути увагу концерну "EMI". До того часу у Білла вже з'явився перший, ще нестабільний акомпануючий склад під назвою "Flagship".
Ансамбль проіснував до лютого 1972 року, ставши прообразом групи "Be-bop deluxe": Нельсон, Паркін і Брайан, до яких додалися Чаттертон-Дью, а також старий знайомий Річард Браун. Вони виконували жорсткий рок з акцентом на соло-гітару. Через чотири дні після появи "Be-bop deluxe" надійшла пропозиція від дочки "EMI" - "Harvest". Компанія була незадоволена представленими плівками і висунула умову: музиканти повинні ще деякий час порепетирувати і пограти "вживу", тому першу сорокап'ятку "Teenage Archangel" / "Jets At Dawn" ансамбль випустив в 1972 році ще на фірмі "Smile Records", рік тому опублікувала сольний лонгплей Нельсона.
Рік потому групі було дано "зелене світло" на запис дебютного альбому. Незадовго до початку роботи над "Axe Victim" пішов Річард Браун. На цьому альбомі "Be-bop deluxe" зайнялися розробкою теми хаотичного майбутнього планети з її дегуманізацією і технологічним екстазом. У 1974 році група зробила перше велике турне з "Cockney rebel". У серпні Нельсон, не задоволений акомпануючим музикантами розпустив команду. З що знаходиться в такому ж роздраю "Cockney rebel" Білл ввів басиста Пола Джеффріса і клавішника Мілтона Риму-Джеймса, а також колишнього барабанщика "Hackensack" Саймона Фокса. Джеффріс і Рим-Джеймс в групі не прижилися. Нельсон оголосив про прослуховування нових кандидатів. У результаті в штат ансамблю був зарахований басист Чарлі Тумахай з Нової Зеландії. Нельсон все ще шукав клавішника. Терміни випуску другої платівки підганяли, і він вирішив сам виконати всі партії клавішних, але в останній момент згадав про знайомого музиканта на ім'я Саймон Ендрю Кларк (нар. 1957), якого запросив до себе.
Кларк не встигав розучити новий матеріал, тому до запису платівки "Futurama" музиканти приступили втрьох. Цей лонгплей добре прийняла критика в Англії, він також удостоївся кількох позитивних рецензій у США, ставши їх першим альбомом, що вийшов в Америці. Нельсон самостійно продюсував амбітний альбом "Sunburst Finish", на три місяці злетів в Англії до 17 місця. Ця платівка стала першою, на якій грав Кларк. З таким складом (Нельсон, Кларк, Тумахай і Фокс) записувалися і всі інші альбоми.
Диск довів: група у відмінній формі (чого варті лише дві пісні - "Fair Exchange" і "Ships In The Night") і знаходиться на шляху до творчого піку, що тільки підтвердило що почалося в березні турне по США і Канаді з "Blue oyster cult ". Альбом "Modern Music" в музичному відношенні був незрівнянно сильніше попередника. Він шість тижнів займав 12 рядок англійських чартів (і тільки 88 - в штатівських). У 1977 році під час третього турне по США і Канаді - на цей раз в якості хедлайнерів - був записаний подвійний концертний альбом "Live! In The Air Age", чотири сторони якого зайняли всього лише сім композицій. Можливо, інертність ансамблю пояснювалася невгамовністю Білла Нельсона, який висловлював невдоволення записуваних матеріалом. В інтерв'ю він заявляв, що турне на підтримку концертної платівки позначило завершення однієї фази існування "Be-bop deluxe", і найближчим часом він представить увазі публіки нову концепцію.
Наступний диск групи, "Drastic Plastic", в корені відрізнявся від попередніх. Його тематичні елементи пов'язував новий для Нельсона інструмент - синтезатор. Звучання диска вийшло близьким до "нової хвилі". Незважаючи на відмінну якість музики і теплий прийом критики, для більшості шанувальників групи обрана стилістика виявилася вражаючою: фани звикли бачити в Нельсона відмінного гітариста-шоумена, готового розважати публіку своєю віртуозною грою. Сам Білл Нельсон не хотів двічі входити в одну річку. 13 серпня 1978 він оголосив про розпуск групи. За його словами, лише одна сольна кар'єра могла дати можливість бути до кінця відвертим.