Деревня Новоалтыбаево тесно связана с д. Кангильдино («Алтыбаево тож»). 30 июня 1731 г. житель д. Кангильдино татарин Баймет Мухаметов объявил в Уфимской провинциальной канцелярии крепостных дел и просил следующую запись подтвердить: «Се яз Кудаш Кашпердин сын III и Киле Кашпердин сын Уфимского уезда Осинской дороги Иланской волости д. Кошманакова башкирцы дали на Уфе сию запись тое же дороги д. Кангильдино ясачному татарину Тойгузе Толубаеву сыну в том, что в нынешнем 7204-м (1696) году июня 14 дня отдали мы, Кудаш и Киле ...владеть ему вечно вотчиною свою в Уфимском уезде Осинской дороги в межах Танаша ... вотчина смежна Учпилинской (т.е. Эске-Еланской) волости з башкирцы меж речки Аралачи и меж речки Узи и Кодушлею ... Платить Тойгузе нам по кунице» (в год).
Д. Новоалтыбаево («Новокангильдино тож») возникла как выселок из коренной деревни Старокангильдино (Алтыбаево) и ее жители на право владения или пользования землей представили договорную запись 1696 г., но получили отказ от губернских властей, которые признали законным актом для этого запись 30 июня 1731 г., утвержденную или засвидетельствованную в 1746 г.
А теперь о времени возникновения дочерней деревни. Впервые она упоминается в материалах V ревизии 1795 г., когда в ней насчитывалось 46 тептярей. В 1920 г. проживало 307 татар при 59 дворах.