While Jewish law applies patrilineal descent to other nations (Yevamos 78b), Nachmanides writes that matrilineal descent applied to the Jewish people from the time of Avraham and onwards (Commentary to Vayikra 24:10). This is justified by the existence of some degree of Israelite nationhood from the time of the Patriarchs, which is suggested by the Talmud's reference to Esav as legally an Israelite (Kiddushin 18a).
However, Nachmanides also cites the French rabbis as being of the opinion that the switch from patrilineal to matrilineal descent occurred at the time of the giving of the Torah at Mount Sinai. This opinion interprets the Midrash (Sifra on Emor, 14:1), which writes that the "son of the Israelite woman" converted, as implying that anyone born before the giving of the Torah who was not a member of the Children of Israel via patrilineal descent needed to convert. This is different from the conversion-type rituals that the other Israelites performed at Mount Sinai (Kerisus 9a), which formalized their de facto status.