ヴァン・ヴリートは、自分のステージ名を当時ザッパと共同で制作していた低予算のSF映画Captain Beefheart vs. The Grunt People[6][7]の登場人物名であるキャプテン・ビーフハート、バンド名をキャプテン・ビーフハート・アンド・ヒズ・マジック・バンドにした。やがてモーテンセンがベトナム戦争に徴兵されたので、セント・クレアはリチャード・ヘプナー(ギター)を加入させて自分はドラムスを担当した[8]。1966年、キャプテン・ビーフハート・アンド・ヒズ・マジック・バンドはヴァン・ヴリート(ボーカル、ハーモニカ)、セント・クレア(ドラムス)、ムーン(ギター)、ヘプナー(ギター)、ハンドレー(ベース・ギター)の顔ぶれで、A&M・レコードから2作のシングルを発表[9]。その後へプナ―は脱退し、ブレイクリーが再加入して彼はドラマーからギタリストに戻った[10]。彼等は新設のブッダ・レコードと契約を結び、ブレイクリーに代わるドラマーにジョン・フレンチを迎えて、翌1967年、デビュー・アルバムの制作へと向かっていった[11]。
キャプテン・ビーフハート・アンド・ヒズ・マジック・バンドとキャプテン・ビーフハート・アンド・ザ・マジック・バンドにヴァン・ヴリートに次いで長く在籍したフレンチは、著書"Beefheart: Through The Eyes of Magic"を彼に捧げて、彼を「全てを始めた人物」と呼んでいる[16]。ムーンは同書でフレンチに応じて、グループが結成された当初はヴァン・ヴリートではなく彼が主導権を握っていたと回想している[17]。
^キャプテン・ビーフハート・アンド・ヒズ・マジック・バンドはセント・クレアが在籍していた1967年にIt Comes To You In A Plain Brown Wrapperと題した2作目のアルバムを制作したが、彼等が当時在籍していたブッダ・レコードは、このアルバムの制作を中止させ録音された音源を全てお蔵入りにした。1971年、ブッダ・レコードはこれらの音源の一部をアルバム『ミラー・マン』として発表した。