Potreba za jednim izvršnim tijelom koje bi bilo iznad svih ostalih tijela na čitavom svijetu je postala očita na početku 20. stoljeća i povećanom popularnošću međunarodnih utakmica. Engleski nogometni savez se mnogo puta sastajao s namjerom osnivanja takvog tijela, ali nije bilo značajnijeg pomaka zbog činjenice da je za takvu organizaciju potrebno više nogometnih nacija. FIFA je osnovana u Parizu, 21. svibnja 1904. Francuski se akronim održao i do danas, čak i izvan država s francuskim kao materinjim jezikom. Prvi predsjednik je bio Robert Guérin.
FIFA je bila izvršno tijelo prvog međunarodnog turnira 1906., no takvo natjecanje nije doživjelo uspjeh. Ovaj neuspjeh kombiniran s ekonomskim faktorima je doveo do smjene Guérina i postavljanja Daniela Burleya Woolfalla, Engleza, za novog predsjednika. Iduće natjecanje, ono na Olimpijskim igrama 1908. je bilo uspješnije, bez obzira što su nastupili profesionalci koje je FIFA zabranjivala.
Članstvo u FIFA-i se tražilo i izvan Europe. Tako je 1909. savez JAR-a zatražio članstvo, Argentinci 1912., a Nogometni savez SAD-a 1913.
Tijekom Prvog svjetskog rata FIFA je izgubila mnogo na polju igrača, jer je većina morala u rat. To je automatski značilo da će se rjeđe putovati na međunarodne utakmice. Poslije rata, predsjednik je postao Carl Hirschmann, Nizozemac, koji je FIFA-u sačuvao od propasti, no pod cijenu povlačenja država iz Velike Britanije, koje su na taj način obznanile da ne žele imati veze s protivnicima iz rata.
1946. je donijela povratak država s Otoka. 10. svibnja 1947. je odigrana utakmica stoljeća između Odabranog sastava Ujedinjenog Kraljevstva i Jedanaestorice iz ostatka Europe na stadionu Hampden Park u Glasgowu, Škotska. Odabrani sastav UK je pobijedio s 6-1 pred 135.000 gledatelja. Čitav utržak od prodanih karata je proslijeđen na račun FIFA-e da se održi i nakon Drugog svjetskog rata. I doista, FIFA je nastavila s radom i organizirala SP-u 1950. u Brazilu. Na svoju pedesetu godišnjicu (1954.) FIFA je imala 84 člana.