Did the Jews wear tfillin in the desert??
Of course they did! Why wouldn't they?? Well, two of the parshiyos in the tefillin weren't said until right before they entered into Israel in the 40th year of their sojourn in the desert. Some want to suggest that tfillin were worn in the desert that contained only two of the four parshiyos [kadesh and vi-haya ki yiviacha, excluding shema and vi-haya im shamoa]. This is difficult to say.
There is a Rashba in Menachos [34a] who says in his first approach that the parshiyos of shema and vi-haya im shamoa were not given until the end of the forty years, while according to his second approach these two parshiyos were given already when they left Egypt and were only said in the Torah much later. Accordong to the second approach it would seem that they were obligated in tfillin from the beginning. According to the first approach, since they didn't have the necessary parshiyos it would seem that they were exempt [although he doesn't say so explicity and one could argue that they were obligated in tfillin with the first two parshiyos].
The Yalkut Shimoni [Shlach remez תש"נ] clearly states that they wore tefillin in the desert as do other medrashim [Shir hashirim 4/2 and 6/6]. That would fit in nicely with the second approach of the Rashba.
In Menachos there is a machlokes how we know that there are four compartments in the tfillin. According to Rebbe Yishmael we know this from the fact that it says טטפת three times - once [in Dvarim] with a vav and twice [once in Shmos and once in Dvarim] without a vav. According to Rebbe Akiva we know that there are four parshiyos from the fact that טט menas two and פת means two, equaling 4. It would emerge that accoרding to Rebbe Akiva there were already 4 parshiyos from the very beginning [in Parshas Bo where it first says טטפת]. According to Rebbe Yishmael the four parshiyos were only derived from later psukim and thus tfillin as we know them didn't exist until the end of the 40 years in the desert.
עיין בספר משנת חיים ע"ס דברים סימן כז, שו"ת דברי יציב ליקוטים סי' ו, הדרת מלך [זילברברג] סי' כה, חבצלת השרון פרשת בא, קובץ קול התורה סג, וגם האדמו"ר מחב"ד דן בזה בכמה מקומות בשיחותיו, משאת כפי עמ' קפט