It had occurred to me that I didn't know when Tefillin were first put into use within Judaism. The specifics of the tefillin are not found in the written text of the Torah and the typical Orthodox response to this is because this is an example of something which is only found in the Oral Law. And, they would say, that it actually strengthens the claim of the necessary existence of the Oral Law because how else could people know what to do?
In my eyes though, the absence of tefillin in the Torah merely suggests that tefillin was made into custom after the Torah was already written.
Anyway, here are a couple of sources I found useful. Though the story of tefillin remains unclear as sources have been lost and the origins are so long ago, there is a general understanding of what they probably were.
See here - History of Tefillin
Interesting things from the site:
DATE OF TEFILLIN.
Rabbi Judah ben Bathyra claimed that he had Tefillin dating back to the time of Ezekiel.3. This is probably an exaggeration, but the custom is clearly very old. Some of the earliest examples of Hebrew writing to survive are fragments from Tefillin. Tefillin were found in the Qumran caves dating from about the 1st cent. BCE. And the Nash Papyrus of the 2nd. cent. CE is another example. Josephus refers to them 4. as does the New Testament.5. The New Testament refers to them using the Greek word Phylacteries. This is not an accurate translation. Because a phylactery is an amulet, which usually means a protection from evil, while Tefillin are used for ritual connected with prayer and are not thought of as protective.
(3.) San. 92b. (4.) Antiquities 4, 8, 13. (5.) Matthiew 23, 5.
HISTORY OF TEFILLIN.
Originally, there were different practices as to which texts were included in Tefillin. The most important source passage was Deut. 6, 4-9. There it says These words which I command you this day...You shall bind them for a sign upon your hands, etc. The question was what does these words refer to? Many thought they referred to Deut 6, 4-5 which said Hear O Israel, the Lord our God, the Lord is one. And you shall love the Lord your God with all your heart and all your soul and with all your might. For this has always been the key belief of Judaism. However many others pointed out that Deut. Chapter 5 which precedes the passage contains the Ten Commandments, and that These words refers to them. A number of the early Tefillin found therefore contain the Ten Commandments. There is evidence that originally the Ten Commandments used to be recited with the three paragraphs of the Sh'ma in the Temple. During the Talmudic period the practice ceased lest sectarians might say that only these Ten commandments had Divine authority and not the remaining 603 of them.7.
The Talmudic Rabbis recognised stages of development in the use of Tefillin. They stated that although the use of Tefillin was a biblical commandment, the precise details of exactly how to carry it out were the work of the later scribes.8. There is also evidence that Tefillin were worn all day.9.
(6.) Tam. 5, 1. (7.) Ber. 12a. (8.) San. 88b. (9.) Men. 36a.
Despite the long tradition of donning Tefillin, it is quite likely that the four proof texts contained in them were not intended to be taken literally. Exodus 13,9 says And it shall be for you as a sign upon your hand and as a reminder between your eyes in order that the Torah shall be in your mouth. It is clear that this did not mean that the written text of the Torah was to be put in the mouth. And if this was so, then equally the written text was not required to be put on our arms and foreheads. Rabbi Simeon ben Meir (Rashbam), the grandson of Rashi and brother of Rabbenu Tam, took this view. He said that the plain meaning is that it should be as a perpetual reminder as if it were written upon your hand.12.
This understood the passages to teach that putting these words between our eyes meant that we should think about the commandments. And that binding them on our hands meant that our deeds should be carrying out the commandments. Such an interpretation gives the verses a far more important meaning. Instead of being just a command to carry out rituals with little leather boxes when we say our morning prayers, they were now seen as commanding us to carry out God's teachings in every thing we do in life. As a result the literal interpretation has tended to trivialise some deeply religious verses.
(12.) Rashbam on Ex 13, 9.
And also here - Jewish Encyclopedia
In regard to their origin, however, the custom of wearing protecting coverings on the head and hands must be borne in mind. Saul's way of appearing in battle, with a crown on his head and wearing bracelets, is connected with this idea. The Proverbs reflect popular conceptions, for they originated in great part with the people, or were addressed to them. Prov. i. 9, iii. 3, vi. 21, and vii. 3 (comp. Jer. xvii. 1, xxxi. 32-33) clearly indicate the custom of wearing some object, with or without inscription, around the neck or near the heart; the actual custom appears in the figure of speech. In view of these facts it may be assumed that Ex. xiii. 9, 16, and Deut. vi. 8, xi. 18 must be interpreted not figuratively but literally; therefore it must be assumed that the custom of wearing strips inscribed with Biblical passages is commanded in the Torah. "Bind them as signs on thy hand, and they shall be as totafot between thy eyes" assumes that totafot were at the time known and in use, but that thenceforth the words of the Torah were to serve as totafot.
Epoch of Introduction.
It is not known whether this command was carried out in the earliest time, and if so, in what manner. But from the relatively large number of regulations referring to the phylacteries—some of them connected with the names of the first tannaim—and also from the fact that among the fifty-five "Sinaitic commands" ("halakah le-Mosheh mi-Sinai") eight refer to the tefillin alone and seven to the tefillin and the Torah together, it follows that they were used as early as the time of the Soferim—the fourth, or at least the third, century B.C. The earliest explicit reference to them that has been preserved—namely, in the Letter of Aristeas (verse 159; see Kautzsch, "Apokryphen," ii. 18)—speaks of them as an old institution.
Josephus ("Ant." iv. 8, § 13) also regards them as an ancient institution, and he curiously enough places the tefillin of the head first, as the Talmud generally does (comp. Justin, "Dial. cum Tryph." ed. Otto, ii. 154). The tefillin are mentioned in connection with Simeon b. Sheṭaḥ, brother-in-law ofAlexander Jannæus (Yer. Ḥag. 77d); and Shammai produces the tefillin of his mother's father (Mek., Bo, § 17 [ed. Friedmann, 21b]; the parallel passage Yer. 'Er. 26a reads "Hillel"). The date here given is the seventh decade of the first century B.C. Schorr (in "He-Ḥaluẓ," vol. iv.) assumes that they were introduced in the Maccabean period, and A. Krochmal regards the reference to Elisha's "wings" (Shab. 44a; Yer. Ber. 4c) as indicating that he was one of the first of the high priests to wear the tefillah ("'Iyyun Tefillah," pp. 27 et seq.). Johanan b. Zakkai never went four ells without tefillin; neither did his pupil Eliezer (Yer. Ber. 4c). Gamaliel II. (c. 100 C.E.) gives directions as to what shall be done with tefillin found on the Sabbath, making a distinction between old and new tefillin ('Er. x. 1), a fact that clearly indicates the extent to which they were used. Even the slaves of this patriarch wore tefillin (Yer. 'Er. 26a). Judah b. Bathyra refers, about 150 C.E., to the tefillin which he inherited from his grandfather; these were inscribed to the dead awakened by Ezekiel (xxxvii.; Sanh. 92b). In the following centuries they were used to an increasing extent, as appears from the numerous sentences and rules referring to them by the authorities of the Babylonian and Palestinian Talmuds.
Tefillin resembled amulets in their earliest form, strips of parchment in a leather case, which is called either "bag" or "little house." Tefillin and "ḳeme'ot" are, in fact, often mentioned side by side (Shab. vi. 2; Miḳ. vi. 4; Kelim xxiii. 9; et al.), and were liable to be mistaken one for the other ('Er. x. 1 et al.). As in the case of the Torah roll, the only permissible material was parchment, while the "mezuzah" was made of a different kind of parchment (Shab. viii. 3 et al.); for this reason a discarded tefillah could be made into a mezuzah, but not vice versa (Men. 32a). It was made square, not round (Meg. iv. 8). The head-tefillah consisted of four strips in four compartments, while the hand-tefillah consisted of one strip. The former could be made out of the latter, but not vice versa; and they were independent of each other (Kelim xviii. 8; Men. iii. 7, iv. 1, 34b; Yer. Ḥag. 77d et passim). The heretics had a way of covering the tefillah with gold, wearing it on the sleeve and on the forehead (Meg. iv. 8). The straps (Yad. iii. 3) were made of the same material as the boxes, but could be of any color except blood-red; they were sometimes blue or of a reddish purple (Men. 35a).
The most important tefillah was the head-tefillah (Kelim xviii. 8 et passim). It was put on according to rule (Sheb. iii. 8, 11; Men. 36a) and was worn from morning until night, with the exception of Sabbath and feast-days (Targ. to Ezek. xiii. 10; Men. 36b); some wore tefillin also in the evening, as did Akiba ('Er. 96a), Abbahu (Yer. 'Er. 26a), Rabba and Huna (Men. 36b) during the evening prayer, and Ashi (beginning of 5th cent.).
The head-tefillah was the principal one, because the tefillah worn on the arm was not visible (Men. 37b). A Jew was recognized by the former, which he wore proudly, because, according to Deut. xxviii. 10, all peoples knew thereby that the Name of the Eternal had been pronounced over him (Men. 35b; Targ. Esth. viii. 15; comp. Cant. viii. 1; Ezek. xxiv. 17, 23). Jerome says (on Galatians iv. 22) that the Jews feared to appear in the cities, because they attracted attention; probably they were recognized by the tefillah. It was not worn in times of danger ('Er. x. 1). The law in regard to tefillin, therefore, which did not demand obedience at the peril of life, had not taken such a deep hold upon the people as other laws (Shab. 130a; R. H. 17a; Yer. Ber. 4c; Pesiḳ. R., ed. Friedmann, p. 111b). However, it must not be inferred from this statement that the tefillah was not worn to any great extent (Rodkinson, "Ursprung und Entwickelung des Phylacterien-Ritus bei den Juden," p. 5), but merely that it was not generally worn.
So it would appear that the custom of tefillin is fairly ancient. Likely from before the 4th century BCE. However, as they originally formed is rather different from how they appear today. A small pouch with scraps of parchment perhaps rather than the blocky weights that we have today. Also the custom for how they were worn has also changed. Clearly, the prayers for Shacharit were written after the custom began so their place in prayer was a later addition.
Perhaps they served the same purpose as the yarmulkah does today, as some religious Jews see it. That at serves to show the world that the individual is a Jew and that means that he recognizes God as his ruler. This would be especially true as some wore it all day. Though their original purpose probably had more to do with luck and protection than anything else.
However, it is also suspect that since before the morning prayers were written, there was no set time for tefillin to be worn and so many people simply went without them. Since Shacharit was not composed until after the Exile, people would make up their own prayers and some perhaps would put on their tefillin to get into the proper mood and attire. But their popularity as a regular item that every Jewish boy must have probably didn't come into effect until after the Exile - perhaps even as late as the time of the Mishnah or Gemara.