It has long been controversial whether or not electrochromism with the color change due to applied voltage is caused by small polarons. Recently, the coloration efficiency of Ca-doped BiFeO3 (CBFO) was reported to be more prominent over a wider energy range than that of a conventional oxide. However, only an interpretation based on oxygen vacancy (V-o), which cannot account for the wide energy dependence of absorption, has been attempted. Here, we show that using first-principles hybrid-functional calculations, hole-trap centers in CBFO can be produced by a variety of small hole polarons and bipolarons around substitutional Ca (Ca-Bi) and ultimately play a significant role of color change. The polaron formation is attributed to the fact that up to two excess holes are trapped to enhance the Bi-O sp sigma bond. It is consistent with the experimental results that under the electroforming condition, electrochromism occurs well in the p-type region when CBFO is separated into two discrete regions relatively rich in V-o (n type) and Ca-Bi (p type). We, therefore, propose that identifying the diversity of the carrier-trap polarons provides a crucial clue to a deeper understanding of the origin of electrochromism.