Młodość. I wojna światowa

Pochodził z rodziny ubogich Kozaków dońskich. Jeszcze w dzieciństwie stracił ojca i był wychowywany przez dziadka. W armii rosyjskiej służył początkowo 2 6 baterii gwardii przy pałacu cara w Petersburgu. Podczas I wojny światowej został dwukrotnie odznaczony krzyżem św. Jerzego i raz medalem "Za męstwo", dosłużył się stopnia podchorążego. Po rewolucji lutowej został wybrany dowódcą 6 baterii gwardii, zaś po rewolucji październikowej jego jednostka przeszła na stronę bolszewików, sam Podtiołkow należał przy tym do lewicowych eserowców.

Udział w rewolucji nad Donem

Bolszewicy i inni zwolennicy rewolucji nad Donem jesienią 1917 r. bez przeszkód organizowali się i szybko rośli w siłę. 23 stycznia 1918 r. w stanicy Kamienskiej sformowany został Doński Kozacki Komitet Wojskowo-Rewolucyjny, który wybrał na swojego przewodniczącego Podtiołkowa, a na sekretarza - Michaiła Kriwoszłykowa, również lewicowego eserowca. Komitet nie powstawał w porozumieniu z kierownictwem partii bolszewickiej ani z Radą Komisarzy Ludowych, nie był także w kontakcie ze zmierzającymi na południe Rosji siłami czerwonych pod dowództwem Władimira Antonowa-Owsiejenki. Jak pisze Peter Kenez, zwolennicy komitetu byli przekonani, że znad Donu należy usunąć siły Aleksieja Kaledina i Armii Ochotniczej Ławra Korniłowa, a wówczas w regionie będą mogły współistnieć władza radziecka i kozactwo. Komitet był organizacją ściśle kozacką, odrzucił m.in. ofertę współpracy od zrewolucjonizowanych organizacji robotniczych z dońskich miast. Nie starał się także o poparcie ludności niekozackiej (inogorodnych).

28 stycznia 1918 r. sześcioosobowa delegacja Kozackiego Komitetu Wojskowo-Rewolucyjnego z Podtiołkowem i Kriwoszłykowem na czele spotkała się w Nowoczerkasku z Aleksiejem Kaledinem. Podtiołkow zażądał podczas spotkania oddania całej władzy nad Donem w ręce zrewolucjonizowanych Kozaków, rozwiązania oddziałów wiernych Kaledinowi i usunięcia znad Donu Armii Ochotniczej. Kaledin zakwestionował prawo Komitetu Wojskowo-Rewolucyjnego do mówienia w imieniu wszystkich Kozaków, zgodził się jednak na kontynuowanie negocjacji i czasowe zawieszenie broni. Podczas negocjacji do Podtiołkowa i Kriwoszłykowa dotarła jednak wiadomość, że biały oddział Wasilija Czerniecowa (prawdopodobnie bez wiedzy Kaledina) zajął Kamienską i Millerowo, zmuszając Komitet Rewolucyjny do wycofania się. W tej sytuacji rozmowy zostały zerwane. Wznowione zostały walki; 3 lutego 1918 r. oddział Podtiołkowa rozbił siły Czerniecowa. Kozacy Podtiołkowa otworzyli tym samym nacierającym z zachodu czerwonym oddziałom pod dowództwem Jurija Sablina (jednej z grup wchodzących w skład czerwonych sił południa Rosji pod ogólnym dowództwem Antonowa-Owsiejenki) drogę na Nowoczerkask. Według Siergieja Wołkowa oddział Podtiołkowa wyróżniał się w walkach szczególnym okrucieństwem.

Dońska Republika Radziecka

W kwietniu 1918 na I Zjeździe Rad Obwodu Dońskiego Fiodor Podtiołkow został przewodniczącym Rady Komisarzy Ludowych Dońskiej Republiki Radzieckiej. Jako przewodniczący wydał "Wezwanie do pracującego ludu Republiki Dońskiej", w którym apelował o powszechne poparcie dla nowych władz, jako reprezentantów robotników, chłopstwa i pracujących Kozaków. Znaczenie Podtiołkowa w republice było jednak ograniczone: faktyczną władzę nad Donem objął dowódca czerwonych oddziałów, które zajęły Rostów - Rudolf Siwers, następnie wspólnie z wysłanym przez Antonowa-Owsiejenkę komisarzem Wojciechowskim. Działali oni niezależnie nawet od Rady Komisarzy Ludowych i kierownictwa partii bolszewickiej. Podtiołkow bez powodzenia oprotestowywał decyzje komisarza, który zadekretował natychmiastową nacjonalizację fabryk i kopalń, wprowadził rekwizycje żywności i utrzymywał politykę terroru zainicjowaną przez Siwersa. W krótkim czasie stosunki między Siwersem i Wojciechowskim a Podtiołkowem stały się na tyle złe, że obie strony groziły sobie nawzajem aresztowaniem.

Wojska niemieckie, które wiosną 1918 r. opanowały całe terytorium Ukrainy, 26 kwietnia wkroczyły od strony Ługańska na terytorium dawnego Obwodu Wojska Dońskiego, zaś 1 maja weszły do Taganrogu. Miejscowi bolszewicy postanowili podjąć próbę obrony Dońskiej Republiki Radzieckiej, chociaż Rada Komisarzy Ludowych zalecała im wycofanie się. Ogłosili "wojnę rewolucyjną", planowali obronę Rostowa i masową mobilizację. Nie byli jednak w stanie jej przeprowadzić, gdyż ludność przekonana o rychłym nadejściu Niemców nie słuchała już ich rozkazów.

Podtiołkow wszedł do nadzwyczajnego sztabu obrony republiki razem z Kriwoszłykowem, Sergo Ordżonikidze, I. Doroszewem i W. Kowalowem.. Nie zdając sobie sprawy z tego, jak poważna była zmiana sympatii wśród Kozaków w północnej części republiki (antybolszewickie oddziały kozackie aktywnie działały od początku kwietnia), Fiodor Podtiołkow na polecenie republikańskiego komitetu wykonawczego razem z komisarzem Michaiłem Kriwoszłykowem i 78-osobowym oddziałem udał się tam, by organizować nowe oddziały rewolucyjnego kozactwa. Jego oddział został otoczony przez białych Kozaków w pobliżu chutoru Kałasznikow, rozbrojony i przewieziony do chutoru Ponomariow, gdzie Kozacy postanowili przeprowadzić zbiorową egzekucję jeńców. Fiodor Podtiołkow i Michaił Kriwoszłykow zostali powieszeni, a ich żołnierze rozstrzelani. Pochowano ich w chutorze w zbiorowym grobie.