Hom-bialgebras and Hom-Hopf algebras are generalizations of bialgebra and Hopf algebra structures, where associativity and coassociativity conditions are twisted by a homomorphism. The purpose of this paper is to define a Gerstenhaber-Schack cohomology complex for Hom-bialgebras and then study one parameter formal deformations.