There are a number of issues that make answering this question quite difficult. Censuses were established at different times in different places, were not always accurate, and were rather different in who was and was not included (e.g., women? Children? Slaves?). In addition, the definition of a "city" varied from place to place and time to time.

For that reason, while Rome is usually mentioned as the first one to surpass one million, and it probably was, it's not easy to prove. Moreover, the rather common contention that London was the next city to surpass one million after the decline of Rome (Alexandria notwithstanding) is probably wrong since there are a number of contenders for this position, like Baghdad, Chang'an, and Angkor. For example, the population of Chang'an was recorded (in 新唐書) in the Tang dynasty as almost 2 million, but this was inclusive of some nearby small cities as well, so we can't tell how many would be in Chang'an proper, nor really define what Chang'an proper was for that matter.