По происхождению — крещёный калмык. Ф. И. Шелудяк принял активное участие в казацко-крестьянском восстания под руководством С. Т. Разина.
Весной 1670 года атаман Ф. Шелудяк командовал конными отрядами восставших казаков в походе от Царицына к Чёрному Яру, а в июне того же года принял участие во взятии Астрахани. Степан Разин поручил начальство над Астраханью атаманам Василию Усу и Фёдору Шелудяку.
Когда весной 1671 года разнеслась весть, что Степан Разин под Симбирском разбит царскими воеводами, Фёдор Шелудяк, вместе с другими атаманами, надумал идти на Симбирск и поплыл вверх по Волге. В начале мая 1671 года Ф. Шелудяк отправил в Астрахань отряд из 500 человек под командованием Степана Кочановского. Вместе с ним он передал Василию Усу, что по дороге на Симбирску он получил сведения о враждебных действиях митрополита Иосифа, его отношениях с царским правительством и воеводами окрестных городов, с донскими и терскими казаками.
11 мая 1671 года атаман Василий Ус созвал казачий круг в Астрахани, куда был вызван митрополит Иосиф. По приговору круга митрополит Иосиф, был обвинён во лжи и измене, и сброшен с раската крепостной башни. В середине мая в Астрахани казаки разгромили дворы дворян, детей боярских, подьячих, крупных посадских людей, духовенства. Был казнён оставленный Разиным в живых второй воевода Астрахани стольник, князь Семён Иванович Львов, а с ним и другие «нарочитые люди».
В июне в Астрахань пришло известие о казни Степана Разина в Москве, и это сильно подорвало боевой дух восставших. Тем не менее, 9 июня 1671 года Шелудяк с повстанческим отрядом осадил Симбирск. Повстанцы предприняли два штурма, которые были отбиты. Обороной города руководил царский воевода Пётр Васильевич Шереметев Большой, располагавший значительными силами. Он также призвал на помощь полк ратных людей из-под Тетюшей, который должен был вскоре прибыть. Во время двух приступов повстанцы понесли крупные потери. Тем не менее, Ф. Шелудяк предпринял ещё одну попытку взять город. Повстанцы, используя возведённые ещё по указанию Разина вокруг стен кремля земляные укрепления, бросились на штурм. В это время подошедший отряд царских ратников под руководством полковника Колобова ударил в тыл осаждавшим и вынудил их отступить.