The idea predates Stoics and is rooted in Greek mythology, the three Moirai ("apportioners"), goddesses of Fate, weave everybody's thread of life, and cut it, so that the nature may take its course without obstruction. Historians link beliefs in fate in many early societies to a largely helpless position of people who felt themselves like playthings at the mercy of external forces driven towards preordained ends. Heraclitus says for example that "eon [time] is like a child rolling dice, sometimes winning, sometimes losing".
Stoics had a more specific philosophical reason however, connected to the so-called logical fatalism, an argument for which was first put forth by Diodorus Cronus. Aristotle's retelling of it involves tomorrow's sea battle, which either will or will not happen. Whichever it is will be true, therefore already is true, since the truth is eternal and immutable. While Aristotle looked for a way out of this conclusion, and leaned towards the opinion of Epicurus that statements about the future have no truth value, Stoics accepted it, and even built a theory of human action and free will around it, an early form of compatibilism. Chrysippus, the head of Stoic school, who also anticipated modern propositional logic, and was considered by many in antiquity Aristotle's equal, gives an argument for the logical fatalism as follows:
"If any motion exists without a cause, then not every proposition will be either true or false. For that which has not efficient causes is neither true nor false. But every proposition is either true or false. Therefore, there is no motion without a cause. And if this is so, then all effects owe their existence to prior causes. And if this is so, all things happen by fate. It follows therefore that whatever happens, happens by fate".
Since the Stoic fatalism works through unbreakable causal chains they essentially equate it to what we now call determinism (the term only became common in the middle of 19th century). This raised the problems of will and responsibility. In response, Chrysippus introduced internal and external causes, and distinguished actions caused through internal character from those caused directly by external forces. It is for the former that we are responsible, according to him, although both of course are fully predetermined.