What led us to believe that space and time are actually interconnected? How did the idea actually originate? why do we believe that this concept is true?
Relativity tells us that when under high enough gravitational fields or high enough speeds, the dynamic nature of time arises. That means that for an observer, you could be in some place in space (that seems normal) but also in some place in time (which is the counterintuitive part).
Therefore, you would have coordinates not only for space, but also in time (search for "spacetime diagram").
Having another coordinate means having another dimension, so we consider time to be another dimension, all of that is motivated by it's dynamic nature.
On the other hand, Newton considered time to be absolute for everybody, that means that everybody would have the same coordinate in time, thus, it makes no sense to consider it another dimension.