Cytochrome b5 (cyt b5) holds heme using two axial histidines, His63 and His39, that are located in the centers of the two heme-binding loops. The previous NMR study on the apo form of cyt b5 (apocyt b5) revealed that the loop including His63 exhibits a larger fluctuation compared to the other loop including His39 [Falzone, C. J., Mayer, M. R., Whiteman, E. L., Moore, C. D., and Lecomte, J. T. (1996) Biochemistry 35, 6519-6526]. To understand the significance of the fluctuation, the heme association and dissociation rates of the two loops were compared using two mutants of cyt b5 in which one of the axial histidines was replaced with leucine. It was demonstrated that the fluctuating loop possesses a significantly slower heme dissociation rate and a faster heme association rate than the other loop. To further verify the importance of the fluctuating loop, the heme association process of wild-type apocyt b5 was investigated using optical absorption and CD spectroscopies. It was indicated that the process proceeds through the two pathways, and that the dominant pathway involves the initial coordination of His63 located in the fluctuating loop. The urea concentration dependency of the rate constants revealed that the folding of the fluctuating loop is associated with the coordination of His63. It was suggested that the fluctuation enables the loop to have a larger heme-loop contact in the heme-bound conformation. The fluctuating heme-binding loops might be useful for the artificial design of heme-binding proteins.