Музыканты, хоть и не виртуозы, были достаточно компетентны — правда, вскоре выяснилось, что у их первоначального барабанщика П. Дж. Блейкли проблемы с держанием ритма, и он ушёл. Очевидной заменой стал Вик Мортенсен, и группа, взявшая имя «Капитан Бифхарт и Его Волшебный Ансамбль», в 1965 г. серьёзно взялась за дело. В фильме Заппы персонаж по имени Капитан Бычье Сердце считался «волшебником», так что это был его волшебный ансамбль. Влит взял этого своего спорного персонажа и поставил его в новое музыкальное измерение. Однако, хотя он и был фронтменом, группу основал Снауффер, который был лидером во всех отношениях — по крайней мере, вначале. Он решил отказаться от своей фамилии, заменив её на своё среднее имя (Клер), которое он также изменил на Сент-Клер. Влит последовал примеру, добавив к своей фамилии приставку Ван. В следующем году, в духе типичного для шестидесятых дурачества, Сент-Клер/Снауффер утверждал, что им пришлось изменить имена, т. к. их разыскивала полиция за то, что они «занимались контрабандным провозом губок в Неваду».[28]
В разное время ходило множество объяснений происхождения имени «Капитан Бифхарт» и истории его принятия в качестве названия группы. Заппа утверждал, что он назвал персонажа фильма по ассоциации с одним из дядьёв Ван Влита, известным как Полковник. Одной из его привычек было пользоваться туалетом, не закрывая дверь — особенно если рядом должна была пройти девушка Ван Влита — и оповещать всех, что его «приятель» (по выражению Заппы) имеет такие благородные очертания, что его конец выглядит как бычье сердце. Другие объяснения и теории говорят, что тут есть какая-то связь с помидором, или что название группы пришло на ум Ван Влиту и/или Заппе и/или каким-то другим участникам группы во время пьяной/обдолбанной экскурсии в пустыню. Позже Ван Влит увёл разговор о значении его псевдонима в сторону от фаллического гротеска, сказав, что он вообще ни к чему не имеет конкретного отношения. Ещё на более поздних стадиях своей карьеры он объяснял, что псевдоним произошёл от недовольства (beef) миром и сопутствующим ему злом, лежащего в его сердце.
Первое живое выступление Капитана Бифхарта и Его Волшебного Ансамбля, по утверждению пресс-релиза 1966 г., состоялось на шоу «Битва Групп» в колледжах Клермонта и Помоны в начале 1965 г. Приводятся следующие слова Сент-Клера: «Не думаю, что мы понимали, как играть вместе, но знали, что в нас достаточно музыки, чтобы победить группу (название которой утеряно) соперников в конкурсе. Наша мотивация в «Битве Групп» заключалась в уничтожении оппозиции».[29] У Ван Влита была совсем другая версия. Он подтвердил, что Сент-Клер позвонил ему и попросил присоединиться к группе, сказав, что выступление этим вечером. Это побудило Ван Влита признать, что он ничего не знает о музыке, и что его голос будет звучать «по-ослиному». Предположительно, Сент-Клер настоял на своём, и в тот вечер группа сыграла в Ланкастере. Ван Влит признаётся, что во время антракта он, «из-за паранойи», воткнул в усилитель пылесос и проделал какие-то фокусы с мексиканскими прыгучими бобами. «Я делал артистическое шоу, и люди врубились», — заключил он. «Вот это и привело меня на неверную дорогу…»[30]
Как и практически любой начинающей группе в то время, Капитану Бифхарту и Его Волшебному Ансамблю нужно было подготовить для концерта какие-нибудь песни Rolling Stones. Активный певец с губной гармошкой, способный прыгать, как Джаггер, был по сути обязательным компонентом во время Британского «вторжения» Шестидесятых. Они столь успешно ассимилировали этот стиль, что некоторые слушатели были убеждены, что перед ними английская группа. Они начали репетировать дома у Хэндли, а потом у Ван Влита на Кэролсайд-Авеню. От архетипичных гаражных начал им пришлось вскоре отказаться и уйти внутрь дома из-за жалоб соседей. Ван Влит оправдывал исполнение песен Stones необходимостью — быстрый рост популярности группы привёл к тому, что у них не оставалось времени разбираться со своим собственным материалом. Дон Элдридж был певцом-гитаристом из Ланкастера и другом Ван Влита. Он часто присутствовал на ранних репетициях группы. По поводу исполнения песен Rolling Stones он вспоминает, что возложенная на Ван Влита роль Джаггера начинала просто мучить его. «Они уже так наигрались этих песен, что как-то раз Дон так швырнул пластинку с "Get Off My Cloud", что она просвистела у меня мимо уха», — говорит он. «К тому времени он уже просто ненавидел Джаггера».