Po studiach rozpoczął pracę w Mathematical Research Institute (obecnie ) Węgierskiej Akademii Nauk. Nawiązał tam współpracę z Paulem Erdősem, czego pierwszym efektem była ich wspólna praca z 1966 roku On divisibility properties of sequences of integers, opublikowana w Acta Arithmetica. Później opublikowali wspólnie jeszcze ok. 30 artykułów.
Doktorat chciał napisać w Moskwie pod kierunkiem jednego z czołowych matematyków na świecie zajmujących się teorią liczb – Aleksandra Gelfonda, ale przez literówkę w podaniu trafił pod opiekę Izraila Gelfanda, którego tematyka badawcza była Szemerédiemu całkowicie obca. Ostatecznie pozwolono mu napisać doktorat u Gelfanda z kombinatoryki, który obronił na Moskiewskim Uniwersytecie Państwowym im. M.W. Łomonosowa w roku 1970.
Od 1965 roku jest związany zawodowo z Alfréd Rényi Institute of Mathematics, a od 1986 jest (obecnie emerytowanym) State of New Jersey Professor of computer science na Uniwersytecie Rutgersa. Okresowo obejmował stanowiska wizytujące m.in.