New algebras of generalized functions containing Gevrey ultradistributions are introduced. We also study the embeddings of the spaces of Gevrey ultradistributions into such algebras.