Brutes have been part of the Covenant since the first contact with humans on harvest in 2525 , but they never had as much presence in military action as the Elites. In Halo 2 the brutes were first introduced into gameplay, but were expanded and made into something more important from a cannon perspective.
Old answer : they weren't only introduced into the covenant in halo 2 that is just the first time you see they in the halo series.
Well the Covie Fleet in Halo CE comprised of only Elites (instead of Brutes). So that's why you only see Elites and not brutes.
Serena said in the Halo Wars campaign (I don't remember the mission) that Brutes were responsible for the attack on Harvest, which was in 2525. Halo 2 was in 2552, so the Brutes would have been in the Covenant for at least 27 years.