mid-15c., "the proving or finding of guilt of an offense charged," from Late Latin convictionem (nominative convictio) "proof, refutation," noun of action from past-participle stem of convincere "to overcome decisively," from com-, here probably an intensive prefix (see com-), + vincere "to conquer" (from nasalized form of PIE root *weik- (3) "to fight, conquer").
Meaning "mental state of being convinced or fully persuaded" is from 1690s; that of "firm belief, a belief held as proven" is from 1841. In a religious sense, "state of being convinced one has acted in opposition to conscience, admonition of the conscience," from 1670s.