The Gemara in Masechet Menahot (35) cites the ruling of Rabbi Yishak requiring that the straps of the Tefillin be colored black, by force of a Halacha Le’Moshe Mi’Sinai (oral tradition originating from Sinai). After citing this ruling, the Gemara proceeds to question it in light of another source which allows the Tefillin straps to be any color. To resolve this contradiction, the Gemara distinguishes between "Mi’bifnim" and "Mi’bahutz" – the exterior of the straps, and the interior, or back side, of the straps. Rashi (Rabbi Shelomo Yishaki of Troyes, France, 1040-1105) explains that the outer, visible side of the Tefillin must be colored black, but the interior side may be any color. This is, indeed, the view of the majority of the Poskim, that the back of the Tefillin straps may be any color (except red, as it is inappropriate for the straps to appear as though they are stained with blood).

The Rambam (Rabbi Moshe Maimonides, 1135-1204), however, in Hilchot Tefillin (3:14; listen to audio recording for precise citation), writes that it is considered an enhancement ("Noi") of the Tefillin for it to be colored all black, including "the entire strap." The clear implication of the Rambam’s remarks is that although Tefillin are valid if the inside of the strap is not colored black, it is preferable for both sides to be painted black. This also appears to have been the view of the Arizal (Rav Yishak Luria of Safed, 1534-1572), as it is written in Sha’ar Kavanot that the straps should be colored black, without any distinction drawn between the two sides of the straps. Likewise, the Or Zarua (Rabbi Yishak of Vienna, 13th century), in Siman 562, cites Rabbenu Simha as commenting that it is considered a Misva to color even the inside of the straps black. This is also mentioned by the Hesed La’alafim (Rav Eliezer Papo, Bulgaria, 1785-1828).

The Shulhan Aruch, however, makes no mention at all of coloring the inside of the straps black, and the prevalent practice is to paint only the exterior of the straps black, while leaving the interior the natural color of the leather. Already the Ben Ish Hai (Rav Yosef Haim of Baghdad, 1833-1909), in Parashat Hayeh Sara, observes that although according to Kabbalistic teaching both sides of the straps should be black, this was not the common practice in his time. He further notes that among the Kabbalists of Yeshivat Beit-El there were divergent customs in this regard.

Nevertheless, in light of the fact that several prominent authorities – the Rambam, Arizal, Or Zarua and Hesed La’alafim – maintained that it is preferable to color both sides black, one who is ordering Tefillin should ask that both sides of the straps be painted black, particularly in light of the fact that the cost entailed is minimal. Although there is certainly no strict requirement to do so, this would be preferable in order to satisfy all opinions.

Summary: Although the common custom is not to color the inside of the Tefillin straps black, nevertheless, several Poskim considered it a Misva to do so, and thus it is preferable when one orders new Tefillin to have both sides colored black, though this is not strictly required.