According to Ivan Putin's account, it was set up by Tsar Alexander, a contemporary of Queen Victoria, after he learned of the establishment of the Torchwood Institute. (AUDIO: The Torchwood Archive) According to another account, it was established during the reign of his successor, Nicholas II, after the Tunguska Event of 1908 and did not yet have its later name. (PROSE: Trace Memory)
In 1927, a Vondraxian orb was found in Siberia. At some point, someone was exposed to the tachyons inside. The KVI tried to harvest the tachyons, but after the person died, the tachyons were lost. After this, the KVI started studying the history of the Vondraxian Orbs.
By 1967, Kenneth Valentine had defected from Torchwood Institute and had started to help the KVI. They set up a hidden base in Wales. In 1967, Hugo Faulkner had contacted them about Jack Harkness' immortality, so the KVI kidnapped him and Michael Bellini (who happened to be with him at the time). Though they planned to have them both brought to Russia for study, the Vondrax attacked, killing much of the personel and allowing Jack and Michael to escape. The survivors were later arrested by Torchwood. (PROSE: Trace Memory)