Клуб је основан 1914, заслугом новосадских студената. После рата, из Прага је донесен комплет дресова ФК Славије, који су остали заштитни знак Војводине до данашњих дана. Године 1924, заједно са клубом Јуда Макаби, Војводина гради стадион "Карађорђе", према нацрту инжењера и председника клуба Даке Поповића. До тада, и једни и други су играли на стадиону код јодне бање, који је припадао новосадском клубу УТК, који је окупљао мађарску омладину. Стадион "Карађорђе" је и данашњи стадион, а 2. априла 2007. враћено му је старо име "Карађорђе". Резултати:
Иако повремен учесник прве лиге у међуратном периоду, озбиљнију улогу у првој лиги, Војводина је почела да игра педесетих година 20. века. Први озбиљнији резултат је 4. место 1952/53. године. Наредних година, Војводина је редовно побеђивала фаворите, али није успела да освоји титулу. 1955. године је изборен пласман у Митропа куп (претечу купа УЕФА), а остале су запамћене победе против Роме у Новом Саду са 4-1 и у Риму са 5-4. И наредних година, Воша је учествовала у овом купу и остваривала запажене резултате. Тадашња златна генерација је стекла велике симпатије својом лепршавом игром, а најпознатији играчи су били Вујадин Бошков и Тодор Веселиновић.
Почетком 60-тих, извршена је смена генерација и већ 1962. године, Војводина постаје вицешампион. Коначно, 1965/66. године, Воша стиже до прве титуле. Најпознатији играчи овог тима су били Илија Пантелић и Силвестер Такач. У Купу шампиона, Воша стиже до четвртфинала, где је избачена од Селтика из Глазгова, који је те године и освојио овај куп, а једини пораз му је нанела управо Војводина у Новом Саду.
70-тих година, Војводина је често била у самом врху табеле, а 1974/75. године је у последњем колу испустила титулу, оставши на другом месту.
80-те године су биле кризне, кулминирајући испадањем у другу лигу 1985/86. Уследила је реконструкција тима, који се експресно враћа у Прву лигу, а за две сезоне овај нови тим Војводине осваја и титулу 1988-89, у једној од последњих сезона пред распад СФРЈ.
90-те године, Војводина дочекује у смањеној првој лиги СРЈ. У почетку, Војводина важи за "вечитог трећег", стиже до јесење титуле 1994. а умало и до трофеја. Од већих успеха је и пласман у финале купа 1997. године, као и финале Интертото купа 1998. године, да би после разних криза, штрајкова играча и смена руководстава, одређена стабилизација уследила тек 2006. године.
У сезони 2006/07. Војводина заузима треће место у Суперлиги и игра у финалу националног купа а тиме обезбеђује место у Купу УЕФА.
Годину 2007/08. тим започиње против малтешког тима Хибернијанс кога лако добија код куће са 5-1 и у гостима са 2-0. У следећем колу квалификација изгубио је од мадридског Атлетика, резултатима 0-3 у гостима и 1-2 код куће. Већ у следећој сезони 2008/09. клуб је имао најуспешнију првенствену сезону од распада Југославије, завршивши сезону на другом месту, иза Партизана, а испред Црвене звезде, али је имао исти учинак у Европи као и претходне сезоне. У сезони 2009/10. клуб није био толико успешан у првенству, пошто је завршио на 5. месту, али је зато стигао до финала Купа Србије, где је поражен од Црвене звезде са 3:0.
Бивши познати играчи:
* Влада Аврамов
* Милан Белић
* Вујадин Бошков
* Тодор Веселиновић
* Љубомир Воркапић
* Дејан Говедарица
* Љубиша Дунђерски
* Славиша Јокановић
* Душан Мијић
* Рајко Алексић
* Стеван Бена
* Стеван Нештицки
* Синиша Михајловић
* Илија Пантелић
* Милан Степанов
* Силвестер Такач
* Мирослав Тањга
* Добривој Тривић
* Милош Шестић
* Милош Красић
* Милан Јовановић
* Здравко Рајков
* Јосип Пирмајер
* Гојко Качар
Успеси:
* Првенство СФР Југославије
o Првак (2) : 1965/66., 1988/89.
o Друго место (3) : 1956/57., 1961/62., 1974/75.
* Суперлига Србије
o Друго место (1) : 2008/09.
* Национални куп
o Финалиста Купа Југославије (2): 1951., 1996/97.
o Финалиста Купа Србије (3) : 2006/07., 2009/10., 2010/11.
