A protein complex that possesses beta-galactosidase activity, i.e. catalyzes the hydrolysis of terminal non-reducing beta-D-galactose residues in beta-D-galactosides. In E. coli, the complex is a homotetramer; dimeric and hexameric beta-galactosidase complexes have been observed in other species.