Os and Cs have probably been around since time immemorial, and some early descriptions of them exist.1 However, not much can easily be found on the subject until the Renaissance.
The European Renaissance (roughly 14th to 16th centuries) was a time for re-examining past beliefs. One belief that began to be abandoned was the superstitious notion that conditions such as mental illness were caused by the devil, demons, or supernatural forces. This belief was gradually replaced by more naturalistic explanations.
Around this time, a new word for Os and Cs came into usage: scrupulosity.2 The new term was popularized by two 15th-century scholars, Jean Gerson and John Nider, and by Archbishop Antoninus of Florence.3 Nowadays most people think of scrupulosity as meaning obsessive religiosity, but in earlier centuries it encompassed all types of Os and Cs. Another common term for Os and Cs was "scruples."
Superstitious ideas about Os and Cs faded away earlier in some places than in others. Continental Europe seems to have led the way.
1See John Climacus (6th century).
2Here is more on the origin of the term "scrupulosity."
3Antoninus (15th century). See also Collins, 1961, p.58.