По завершении записи Хаскел и Маккалох покинули коллектив, оставив его в безнадёжном положении рок-группы без певца, басиста и ударника.

По продолжительном прослушивании выбор Фриппа и Синфилда остановился на барабанщике Иане Уоллесе и вокалисте Бозе Барреле, которого Фрипп решил также обучить игре на бас-гитаре. По ходу продолжительных гастролей группа в этом составе выпустила четвёртый альбом «Острова» («Islands», 1971), поисковый по характеру и ставший переходным в истории группы — это и прощание с символистской поэзией Питера Синфилда, и первая «ласточка» или, вернее, буревестник грядущей метаморфозы — композиция «Sailor’s Tale», и, конечно, грандиозная концовка диска — прелюдия «Song of the Gulls», и собственно заглавная композиция диска — «Islands», фантастическая по красоте и лиричности, произведение настолько совершенное, что Фрипп окончательно перешёл от фазы «search» к фазе «destroy».

В конце 1971 года коллектив покинул Синфилд. Оставшийся состав продолжал гастролировать в следующем году; записи 1971—1972 гг. вошли в концертный альбом «Земной» («Earthbound», 1972). Состав дорожек этого альбома пересекается с «Островами», и живое исполнение представляется более интересным (несмотря на крайне низкое для официального альбома качество записи).

По окончании гастролей из «King Crimson» ушли Коллинз, Уоллес и Баррел, чтобы сформировать группу «Снейп», и Фрипп вновь начал поиск новых музыкантов.

В группу были приглашены импровизирующий перкуссионист Джеми Мюир, вокалист и басист Джон Уэттон (игравший ранее в Family и знакомый Фриппу со студенческих лет), барабанщик Билл Бруфорд, расставшийся ради игры в нестабильной и непредсказуемой King Crimson с творчески и коммерчески успешным коллективом Yes, и Дэвид Кросс (смычковые, клавишные). Место сочинителя текстов занял Ричард Палмер-Джеймс.

Новый состав начал репетиции и гастроли в конце 1972 года, и уже в начале следующего вышел пятый студийный альбом группы, «Заливное из язычков жаворонка» (Larks' Tongues in Aspic).

«Заливное …» существенно отличается от ранних альбомов группы и представляет собой заметную веху в истории как прогрессивного рока, так и рок-музыки в целом. Его смысловым центром являются три инструментальные пьесы: открывающая и финальная части титульной композиции (Larks' Tongues in Aspic. Part I и Larks' Tongues in Aspic. Part II) и «Говорящий барабан» (Talking Drum). В них впервые проявилась тенденция группы к наращиванию по ходу развития тем ритмической и тембральной сложности на относительно бедном мелодическом материале, характерная для последующего творчества группы.

Альбом включает также энергичную и ритмически усложнённую балладу «Субботняя книга» (Book of Saturday), неожиданно богато модулированную песню «Изгнанники» (Exiles) и странную полиметричную песню «Легкие деньги» (Easy Money). Уникально для этого альбома дополнение барабанов перкуссией Мюира, создающее весьма сложный метрико-ритмический узор ударных инструментов.

Несмотря на студийный характер записи, «Заливное …» подчёркивает импровизационную составляющую творчества группы. Ещё более отчётливо она проявляется в записях тех лет, обнародованных в конце девяностых на дисках коллекционной серии («Живьем в Джексонвиле» (Live at Jacksonville, 1998), «Бит-клуб» (The Beat Club, 1999) и др.).

В 1973 году, в начале которого группу покинул Мюир, King Crimson продолжала гастроли по Британии, континентальной Европе и Америке.