We first introduce an algebra of almost periodic generalized ultradistributions containing classical almost periodic ultradistributions as well as the algebra of almost periodic generalized functions, and then we study the fundamental properties of this algebra.