U lind në Libohovë, në një familje atdhetare. I ati ishte Qehaja i familjes së Arsllan-Pashalinjve, oxhakut të Libohovës.
Mësimet e para i mori në vendlindje, më pas vazhdoi Normalen e Elbasanit dhe pastaj kolegjin e Shën Mitër Korone në Itali, kurse studimet e larta për pedagogji i filloi në Universitetin e Romës.
Më 1908 braktisi bankat e shkollës për t’u bashkuar me çetën e Çerçiz Topullit. Më 1910 tentoi për të vrarë në Shkodër komandantin e ekspeditës ushtarake osmane, gjeneral Shefqet Turgut pashën. Më 1914 u radhit në forcat shqiptare për çlirimin e Shqipërisë së Jugut nga pushtimi i forcave greke.
Gjatë veprimtarisë së tij, më 1910, ai punoi si mësues në Libohovë, në Tragjas të Vlorës më 1913, dhe në Tepelenë e në Vlorë në vitet 1916-1918. Më 1918 me nismën e tij, u formua në Vlorë shoqëria atdhetare e rinisë vlonjate me emrin “Djalëria e Vlorës” dhe në krye të saj organizoi demonstratën e 28 nëntorit 1918 kundër pushtuesve italianë.
Në pranverë të vitit 1919 në Shën Mitër krijoi “Lidhjen e Rinisë Shqiptare”, për mbrojtjen e të drejtave kombëtare kurse më 13 qershor 1920 vrau me atentat në Paris, Esat Pashë Toptanin.
Gazeta e njohur franceze “Le Meiroir”, më datë 20 qershor 1920 publikoi një fotografi të panjohur deri me sot të Avni Rustemit.
Në këtë foto, ai shihet i torturuar barbaishtë nga policia franceze pasi kishte kryer atentat ndaj Esat Pashë Toptanit në Paris. Megjithatë, Avni Rrustemi u lirua pas vetëm 6 muajve.
Me rikthimin e Avni Rustemit në Shqipëri, veprimtaria e tij politike vjen duke u intensifikuar. Pikërisht, më dhjetor 1920 ai filloi punën për bashkimin e shoqërive demokratike ekzistuese në një organizatë të vetme. Kongresi i mbajtur më 25 prill 1921 në Vlorë krijoi një shoqëri, që mori emrin federata “Atdheu”. Kryetar nderi i saj u zgjodh Avni Rustemi.
Me nismën e tij u krijuan dhe organizata profesionale të mësuesve. Pas mbylljes së federatës “Atdheu”, në gusht 1922, përsëri me nismën e Avni Rustemit, më 13 tetor 1922 u krijua në Tiranë shoqëria demokratike “Bashkimi”.
Avni Rustemi, nuk qe vetëm organizatori kryesor i shoqërive demokratike, por edhe një ndër ideologët më të shquar demokratë. Daljen e vendit nga prapambetja, Avni Rustemi e shikonte në zhvillimin e ekonomisë së pavarur kombëtare. “Pa pavarësi ekonomike, – shkruan ai, – nuk mund të ketë pavarësi politike”.
Idetë e tij demokratike e revolucionare ai i shprehu edhe në Asamblenë Kushtetuese të vitit 1924, ku u zgjodh deputet nga populli i ish-prefekturës së Kosovës. Ai kritikoi me guxim shpërdorimet e aparatit burokratik të kohës, fudullëkun e injorancën e klasave sunduese reaksionare dhe mbrojti me zjarr traditat e popullit tonë dhe të drejtat e shqiptarëve që jetonin në trojet e veta në Jugosllavi.
Në kushtet e ashpërsimit të kontradiktave klasore e politike të vendit nga njerëz të vënë prej qeverisë së asaj kohe, atij i bëhet atentat më 20 prill 1924 pranë Pazarit të Ri në Tiranë, ku vdes 2 ditë më vonë pikërisht më 22 prill 1924. Vrasja e deputetit shërbeu si shkëndijë e Lëvizjes, që triumfoi më 10 qershor 1924.