The first mention of Simchas Torah is in the Zohar where it says that on Shmini Atzeres they would take all the Sifrei Torah out of the Aron HaKodesh. The Machzor Vitry, 12th century, is the first to mention hakafos, but only in the morning. The Maharam MiRottenberg, 13th, adds hakafos also at night. The Arizal, 16th, is the first to describe specifically 7 hakafos. Interestingly, the Mechaber in Shulchan Aruch does not mention at all the concept of Simchas Torah and describes the second day of Shmini Atzeres as a regular Yom Tov.
The Gemara writes that until after the destruction of the Beis HaMikdash, Rosh Chodesh was determined by witnesses testifying in Beis Din on the appearance of the new moon. Therefore, places distant from Eretz Yisroel would not know if the previous month was 29 of 30 days until after Yom Tov began, and they would always keep two days in doubt which one was the real Yom Tov. Even later after the design of the set calendar, this minhag remained unchanged.