Первое упоминание села сделано в купчей князя Кемского, датированной 1526 годом.
Названия реки и села станут понятны, если учесть, что когда-то эти земли населяли финно-угорские племена. В переводе с языка одного из этих племен – древнесаамского – слово Кукобой означает «длинный ручей», а Ухтома – «река с волоком».
Собор Спаса Нерукотворного Образа (1909—1912 гг.), архитектор — Василий Косяков, построен местными мастерами на деньги купца Ивана Агаповича Воронина.
Воронин не забыл своих односельчан, и, приехав в село, предложил им на выбор – строительство собора в Кукобое или железной дороги до Пошехонья (60 километров по непроходимым лесам и болотам). Тогда миряне единодушно выбрали собор, хотя в селе и была добротная действующая церковь в честь Успения Пресвятой Богородицы. На строительство храма Воронин пожертвовал 1 миллион царский рублей.
Храм поражает своей красотой, изумительными пропорциями, богатейшей орнаментикой из белого облицовочного камня. Собор выполнен в традициях так называемого «псевдорусского стиля» - широко распространенного в первой половине XX века.
Это направление в архитектуре основывается, как писал видный историк и археолог И.Е. Забелин (1820 – 1908), на самобытности русского народного зодчества XVI – XVII веков «где своенародные и самобытные черты, … главные мотивы декора». Собор Спаса Нерукотворного стоит в одном ряду с такими представителями этой школы в Москве как Здание Городской Думы (1890-1892 гг.) и исторический музей (1875 – 1881 гг.)
Специально для храма был построен небольшой кирпичный завод. Только облицовочный кирпич – белый для стен и лазуревый для колоколен – доставляли по железной дороге из Финляндии, причем каждый кирпич был отдельно завернут в бумагу и пронумерован. Строительство было завершено за неполных 4 года.
В истории храма примечательно то, что он удостоился быть освященным архиепископом Тихоном, будущим Патриархом Московским и Всея Руси, впоследствии причисленным православной церковью у лику святых. В те годы Тихон возглавлял Ярославскую кафедру. Освящение собора состоялось в мае 1912 года.
Сразу после революции храм был закрыт, а в 30-е годы кресты и колокола были сорваны, роспись уничтожена, прекрасной работы резной иконостас и великолепные иконы варварски изломаны и сожжены. Помещение храма использовалось как склад, а в подвале была устроена тюрьма.
В 1989 году храм был возвращен верующим.
В 2004 году Кукобой был объявлен «родиной Бабы-Яги» — её «день рождения» здесь празднуется 26 июня. Был также создан музей Бабы-Яги («избушка на курьих ножках»). Создание этого бренда дало 13 рабочих мест и сделало село привлекательным туристическим местом. Русская православная церковь выступила с резким осуждением «поклонения Бабе-Яге».