Given a G-structure with connection satisfying a regularity assumption we associate to it a classifying Lie algebroid. This algebroid contains all the information about the equivalence problem and is an example of a G-structure Lie algebroid. We discuss the properties of this algebroid, the G-structure groupoids integrating it and the relationship with Cartans realization problem.