Kutatási területei a halmazelmélet, a topológia, a véges és végtelen kombinatorika voltak. Első eredményeit az axiomatikus halmazelméletben érte el, de később elsősorban a végtelen kombinatorika (más néven kombinatorikus halmazelmélet) területén végzett kutatásokat. Évtizedeken keresztül dolgozott együtt Erdős Pállal, akivel gyakorlatilag létrehozta a kombinatorikus halmazelméletet jellegzetes fogalmaival, módszereivel, sokszor máig megoldatlan kérdéseivel. Ezzel a végtelen kombinatorika nemcsak a halmazelmélet nagy fejezeteinek egyikévé vált, de alaptételeit, definícióit a halmazelmélet más területein is folyamatosan használják, mint például a halmazleképezések Hajnal-féle alaptételét vagy a partíciókalkulust. A véges kombinatorika területén egy jelentős eredménye Erdős Pál egyik sejtésének bebizonyítása a ma már Abel-díjas Szemerédi Endrével. Eszerint, ha egy véges gráfban minden pont foka kisebb k-nál, akkor a gráf egyenletesen kiszínezhető k színnel.
Tudományos munkássága mellett igen sok energiát fektetett oktatási és tudományszervezési tevékenységeibe is. Az ELTE tanáraként fontos szerepe volt a magyar kombinatorikai és halmazelméleti iskolák megteremtésében. Megújította a halmazelmélet és a matematkai logika oktatását. Sós Verával közösen az 1960-as években elindította a híres Hajnal–Sós-szemináriumot, amely valószínűleg a világ első kombinatorikai szemináriuma volt, és ma, fél évszázad után is működik. A szemináriumon számos nemzetközi nagyság oktatott, és sok, később híressé vált eredményt adtak elő magyar matematikusok. Hajnal András tanítványai közül többen ma az MTA tagjai.
Kitűnő szervezőként központi szerepe volt – az amerikai feladatok vállalásáig – a magyar matematikai élet irányításában. 18 éven át volt a Bolyai János Matematikai Társulat meghatározó vezetője
1994 és 2004 között a New Jersey állambeli Rutgers Egyetemen dolgozott, ahol annak kutatóintézetét, a DIMACS-ot (Center for Discrete Mathematics and Theoretical Computer Science) igazgatta.
Munkásságát egyebek mellett 1967-ben Akadémiai Díjjal, 1970-ben Állami Díjjal, 1980-ban Szele Tibor-emlékéremmel, 2013-ban a Magyar Érdemrend középkeresztjével ismerték el.
