Впервые упоминается в летописях под 1429, когда великий князь московский Василий II Васильевич послал своих дядьёв, Андрея и Константина Дмитриевичей, на татар, разоривших и ограбивших окрестности Галича, Кострому, Плёс и Лух. Князья гнались за татарами до Нижнего Новгорода, но не догнали и оставили погоню. Тогда Фёдор Пёстрый с воеводой Ф. К. Добрынским, «съвокупяся с своим дворы», тайком от братьев-князей бросились в погоню по Волге и «угониша зад их» за Нижним Новгородом, «побиша Татар и Бесермен и полон весь отняша, царевича и князя Али бабы не догониша».
В 1431 году был воеводой в походе на волжских и камских болгар, в результате чего окончательно разрушил их столицу Великий Булгар.
Зимой 1471—1472 его послали на камских пермяков, где подверглись нападению и оскорблениям московские люди, чтобы «воевати их [местные племена] за их неисправление». 9 апреля 1472 «на Фоминой неделе в четверг», московские войска подошли к устью реки Чёрная, впадавшей в Весляну (левый приток Камы), и «оттуду поиде на плотах и с конми» дальше, в Пермскую землю, а затем сухим путём, на конях — за Каму, на Чердынь, на пермского князя Михаила Ермолаевича. Решительное сражение произошло на реке Колва, впадающей в Вишеру (левый приток Камы): в плен был взят пермский воевода Кач, после чего был занят Искор — главное святилище пермяков. На слиянии Колвы и её притока Покчи князь Фёдор Пёстрый поставил острог и «приведе всю землю за великого князя», а князя Михаила и пленных его воевод с трофеями отослал в Москву, известие же о победе достигло столицы 26 июня.
В том же году, согласно Никоновской летописи, ходил с коломенцами к Алексину, куда подошёл с большим войском хан Ахмат, затем встречал византийскую царевну Зою Палеолог, будущую великую княгиню московскую Софью Фоминичну.
