Narodil se 5. srpna 1899 v Mostě do rodiny železničního inženýra a vrchního rady čs. státních drah Antonína Vodseďálka. V Mostě žili Vodseďálkovi pouze do listopadu 1903, kdy byl otec služebně přeřazen do nedalekých Loun.

V Lounech dokončil Antonín základní školní docházku, na přání otce poté začal studovat na místním reálném učilišti. Brzy však přestoupil na lounské gymnázium, po jehož absolvování se začal připravovat na vysokoškolská studia v Praze. V té době však zuřily boje 1. světové války, a proto narukoval jako dobrovolník do rakousko-uherské armády, v jejíchž řadách sloužil až do října 1918. Po návratu do vlasti se začal politicky angažovat – stal se členem mládežnické organizace České státoprávní demokracie (v březnu 1919 přejmenované na Čsl. národní demokracii), v letech 1919–1921 byl dokonce předsedou její pobočky v Lounech.

V roce 1921 začal studovat na Filozofické fakultě UK v Praze a o rok později zahájil i pedagogickou činnost, když nastoupil jako učitel v obci Ledce nedaleko Plzně. V témže roce se oženil s Marií Bieblovou, sestrou budoucího slavného českého básníka Konstantina Biebla. Pod jejím vlivem a vlivem dalších levicových intelektuálů (mj. Ivana Olbrachta) se politicky radikalizoval a brzy připojil se k její komunistické frakci sociální demokracie.

Již na jaře roku 1923 mu bylo kvůli propagaci komunismu zakázáno nadále vykonávat učitelské povolání a dokonce mu hrozilo trestní stíhání. Ani to ho neodradilo od další činnosti, naopak po přestěhování do Prahy dále stupňoval své aktivity v rámci stranické práce. Začátkem roku 1924 pak na základě instrukce ÚV KSČ odešel na Podkarpatskou Rus, načež zanechal vysokoškolských studií. Jeho zdejší působení nakonec trvalo jen něco málo přes rok.

Po úspěšném splnění úkolů ho již v květnu 1925 strana poslala jako okresního tajemníka do Hradce Králové, kde se zároveň stal redaktorem časopisu Pochodeň. I v největším východočeském městě vydržel jen do konce roku 1925, aby se znovu vrátil do Prahy, kde byl půl roku zaměstnán na sovětské obchodní misi působící v Praze. Zřejmě v té době se jako velký idealista rozhodl odejít pracovat přímo do SSSR.

V lednu 1927 navzdory výstrahám svých rodičů odjel do SSSR, aby působil jako učitel v české osadě Česká Krošna (dnes Krošňa) na předměstí Žitomiru. Okamžitě zde začal aktivně pracovat - vedle učení se věnoval rozmanité kulturní a vzdělávací osvětě mezi místními Čechy. Díky své činorodosti a metodickému umu se již v srpnu 1927 stal lektorem českých škol na Institutu lidové osvěty (ILO) s centrem v Kyjevě.

V roce 1927 se rozvedl se svou první manželkou a krátce nato se oženil s Olgou Procházkovou, dcerou českých starousedlíků z České Krošny. V roce 1928 se novomanželům narodil první syn Viktor a o rok později dcera Zinaida (Zina). V souvislosti s represivními akcemi proti rolnickému stavu odmítajícího kolektivizaci zemědělství na počátku 30. let došlo k utlumení samostatných národnostních aktivit, cílem hromadného teroru se stály i národnostní menšiny, vč. Čechů a to zejména na Ukrajině.

V hledáčku sovětské tajné policie se ocitly i učitelé a funkcionáři českého školství na Volyni. V rámci vykonstruovaného případu českých vyzvědačů a nepřátel SSSR, byl orgány OGPU 3. srpna 1930 na ulici v Žitomiru zatčen i Antonín Vodseďálek.

První výslechy probíhaly v Kyjevě. Dne 16. srpna 1930 byl se zvláštní eskortou poslán do Charkova, kde pokračovalo vyšetřování. V průběhu podzimu se vyšetřovatelům podařilo Vodseďálka zlomit a nakonec „přiznal" vše, co od něj požadovali. Celý případ „vyzvědačské organizace československé rozvědky" se nakonec rozrostl do nebývalé šíře. Do celého případu bylo nakonec zahrnuto 37 osob, které byly obviněny z vyzvědačství, kontrarevoluční činnosti ve prospěch Československa a Francie, z agitace proti sovětské vládě a kolektivizaci a z náboženské agitace, ekonomické a vojenské špionáže a diverze. V hlavním a neveřejném procesu, který se konal ve dnech 12.–14. června 1931 v budově OGPU před Nejvyšším soudem SSSR v Charkově, bylo souzeno 21 osob. K nejvyššímu trestu, tedy trestu smrti zastřelením, byl odsouzen Antonín Vodseďálek a ještě dalších devět obžalovaných.

Začátkem prosince 1931 byli všichni odsouzení nejvyššímu trestu odesláni z Charkova do věznice pro politické vězně v Jaroslavli. V srpnu 1933 pak byli transportováni do nechvalně proslulého nápravně pracovního tábora OGPU na Soloveckých ostrovech. V důsledku prožitých fyzických i psychických útrap Vodseďálek dočasně zešílel, nakonec se ale vyléčil. Díky intervencím československého ministerstva zahraničních věcí u sovětských úřadů byl v březnu 1935 Vodseďálkovi i dalším odsouzencům na smrt změněn trest na 10 let odnětí svobody. Naděje na předčasné osvobození A. Vodseďálka zmařilo rozhodnutí lidového komisariátu spravedlnosti z dubna 1937, který definitivně zamítl propuštění vězňů původně odsouzených na smrt.

V roce 1940 byl A. Vodseďálek po vypršení celého desetiletého trestu poslán do vyhnanství do města Kirov na severovýchodě evropské části Ruska. Po dlouhých letech se mu podařilo navázat kontakt s domovem a se svými dvěma dětmi, které byly mezitím umístěny v dětských domovech na Žitomirsku. V Kirově se mu nakonec podařilo získat místo knihovníka ve státním nakladatelství, od nového školního roku měl začít vyučovat na jedné ze zdejších středních škol. Od prosince 1940 navštěvoval kurzy učitelů německého jazyka na místní univerzitě, kde složil i několik zkoušek.

Dne 22. června 1941 napadlo SSSR nacistické Německo, což vyvolalo další vlnu represí proti domnělým špionům a nepřátelským živlům. Již 10. července 1941 zatkli příslušníci kirovské NKVD také A. Vodseďálka a znovu ho obvinili ze špionáže. Mimořádné kolegium při NKVD SSSR kirovské oblasti ho dne 25. července 1942 odsoudilo k dalším 5 letům v nápravně pracovních táborech.

V kirovské věznici byl vězněn až do září 1942, kdy byl deportován do Uchtižemlagu na severu Ruska. Sem již přijel ve špatném zdravotním stavu a v podstatě neschopný práce. V prosinci 1942 byl proto přemístěn v invalidní lagpunkt, od ledna 1943 se léčil v lágrové nemocnici lagpunktu č. 32 lágrového oddělení č. 7 v Uchtě. Antonín Vodseďálek zemřel v důsledku vyčerpání a avitaminózy 9. února 1943. Pohřben je pravděpodobně na bývalém vězeňském hřbitově v Uchtě.