He was born in Varberg, then-Denmark as a son of vicar Laurids Kjeldsen Stub and his wife Margrethe Hansdatter. He attended school in Landskrona and Slagelse before studying at the University of Copenhagen from 1626 to 1628. During a subsequent travel around continental Europe, he volunteered in Brabant to fight for the Holy Roman Empire in the Thirty Years' War. He attained the rank of Captain before quitting in 1631. He was a teacher in Copenhagen for less than a year, before beginning another travel in Europe. This time he volunteered for the Kingdom of France. During 1635, he quit the French army, finished his university education and was appointed as vicar in Christiania, one of the larger towns in Norway.
In 1636, he married the daughter of Christiania bishop Nils Simonssøn Glostrup, but she died in 1641. During the same year Stub lost his job after a dispute with Christiania's burgomaster; Stub instead became vicar of rural Ullensaker. From 1643 to 1645 he participated with the Thirty Years' War for the third time, this time as a counsellor for Hannibal Sehested in the Hannibal War. He had an informal command of those who defended the Norway–Sweden border. He was probably the writer of the description of contemporary events titled Aggershusiske Acters første Quartaels summariske Beskriffuelse paa nerverende Aar 1644 flitteligen samlet oc forfattet.
During 1644 he married a daughter of the burgomaster in Fredriksstad, but she died in 1648. During the 1650s he married his third wife. Kjeld Stub was an ancestor of Christian Stub, Hans Colbjørnsen, Peder Colbjørnsen, Herman Colbjørnsen, Edvard Grieg, Eiler Eilersen Hagerup and Halvdan Koht.
He was vicar in Ullensaker again from 1645 to 1647, then dean of Øvre Romerike and Solør for the rest of his life, despite accusations of various wrongdoings. He was also involved in business, among others Eidsvoll Iron Works. After a driving accident in January 1663, he died in April 1663 in Ullensaker Church while preaching a sermon.
He was a signatory of the 1661 Sovereignty Act, the new constitution of Denmark-Norway, as one of the representatives of the Norwegian clerical estate, one of the two privileged estates of the realm in Denmark-Norway.
- Gjeruldsen, Ole H. "Kjeld Stub". In Helle, Knut (ed.). Norsk biografisk leksikon (in Norwegian). Oslo: Kunnskapsforlaget. Retrieved 5 February 2011.
- Finck, Henry Theophilus (1909). Grieg and His Music. pp. 4–6.
- Koht, Halvdan (1951). Historikar i lære (in Norwegian). Oslo: Grøndahl & Søn. p. 11. (with the Norwegian Historical Association)
- Allan Tønnesen (ed.), Magtens besegling. Enevoldsarveregeringsakterne af 1661 og 1662 underskrevet og beseglet af stænderne i Danmark, Norge, Island og Færøerne, Heraldisk Selskab/Syddansk Universitetsforlag, Odense 2013, ISBN 9788776746612