Rojen je bil v ljubljanskem Kapucinskem predmestju, kjer je bil njegov oče Anton Vojska več let učitelj, njegova mati je bila Elizabeta, roj. Šušteršič. Osnovno šolo in gimnazijo je obiskoval v Ljubljani, nato pa je od leta 1847 na Dunaju študiral matematiko in fiziko. Leta 1850 je najprej promoviral iz filozofije, leta 1852 pa še pravo na univerzi v Gradcu.
Kot odvetniški pripravnik in sodni uradnik je služboval v raznih krajih, najprej v Ljubljani, nato na Dunaju in v Celju. Od leta 1854 do reorganizacije sodišč je služboval v različnih krajih na nekdanjem Ogrskem. Nato se je vrnil v Ljubljano, nekaj časa pa je bil kot pomočnik dodeljen tudi okrajnemu sodišču v Planini. Leta 1867 je najprej postal javni tožilec v Novem mestu, od leta 1869 pa sodni svetnik pri novomeškem okrožnem sodišču. Upokojil se je kot višji sodni svetnik leta 1895.
Vojska je bil navdušen rodoljub. Prizadeval si je za uvedbo slovenščine na sodiščih in bil med sodniki, ki so že okoli leta 1865 uradovali v slovenskem jeziku. Bil je eden izmed najbolj izobraženih Slovencev svojega časa. Dobro je poznal slovensko politično in narodnogospodarsko zgodovino. Govoril je več jezikov in imel doma bogato knjižnico pravniških, zgodovinskih in leposlovnih del, čeprav sam ni pisal. V Novem mestu je bil eden redkih prijateljev pisatelja Janeza Trdine. Bil je njegov informator o pesniku Prešernu, ki ga je osebno poznal še kot ljubljanski dijak.
Njegova vnuka sta bila ekonomist Danilo Vojska in partizanski zdravnik Vlado Vojska.
Dr. Andrej Vojska. Slovenski narod, 17. 2. 1903, let. 36, št. 38, str. 2.
Pol stoletja društva »Pravnik«: Spominska knjiga. Ljubljana: Društvo Pravnik, 1939, str. 53.
Slovenski biografski leksikon: 4. Knj.: Táborská – Žvanut. Ljubljana: Slovenska akademija znanosti in umetnosti, 1980–1991, str. 561.