According to Wookieepedia, the time period between Knights of The Old Republic and The Phantom Menace overlaps with four broad periods of Galactic History:
Old Sith Wars: 4000 BBY1 - 3950 BBY
This period is dominated by conflicts with various Sith Lords (hence the name), and opens with the events of the Tales of the Jedi comic series. Knights of the Old Republic picks up at the tail end of this period, with the main story of the first game starting in 3956 BBY.
Inter-Sith Wars Period: 3950 BBY - 2000 BBY
The events of SW:TOR occur entirely within this period; although we don't know exactly when the game will end, it's probably safe to assume that it won't last for two thousand years. The most recent TOR expansion, Shadow of Revan, takes place in 3640 BBY.
There's very little fiction that takes place during this period; most of the information we have on it comes from The Essential Atlas, which was intended to be a definitive source for planetary information. Some information can also be found in material related to The Old Republic MMO, especially in-game codex entries.
Draggulch Period: 2000 BBY - c. 1000 BBY
This period coincides almost entirely with the New Sith Wars, and the last century of this period is sometimes called the Republic Dark Age.
Once again, there's very little fiction set in this period. Most information comes from Essential guides and RPG sourcebooks.
Post-Ruusan Period: c. 1000 BBY - 19 BBY
Also sometimes called the Great Peace of the Republic, Wookieepedia technically calls this the "Fall of the Republic/Rise of the Empire Period." In-universe, this period begins with the Ruusan Reformation, a structural reorganization of the Jedi Order, and the Republic itself to a lesser extent, so significant that it became year 0 in the (in-universe) Galactic calendar. The first 700 or so years of this period is also called the Golden Age of the Old Republic.
The above lists of works are incomplete by design. If you're interested in a more complete list of works, Wookieepedia has a helpful timeline of Legends media
1 Dates in Legends are typically based around the Battle of Yavin, the climactic battle in A New Hope, which is 0 ABY; BBY and ABY mean exactly what you'd expect them to