“Credible” means “believable” or “trustworthy.” It is also used in a more abstract sense, meaning something like “worthy”: “She made a credible lyric soprano.” Don’t confuse “credible” with “credulous,” a much rarer word which means “gullible.” “He was incredulous” means “he didn’t believe it” whereas “he was incredible” means “he was wonderful” (but use the latter expression only in casual speech).

Although you will commonly see it said of some far-fetched story either that “it strains credulity” or that “it strains credibility,” the latter is more traditional. Something that strains credulity would be beyond the powers of even a very gullible person to believe. This form of the saying isn’t very effective because a credulous person isn’t straining to believe things anyway. Such a person believes easily without thinking. It makes more sense to say that something too weird or wild to be credible “strains credibility.”

See also “incredible” and “begs belief.”