In the current research paper, we define and investigate the concept of BiHom-Gerstenhaber algebra. This algebraic structure is defined by two linear maps f, g, a BiHom-commutative law \(''\wedge ''\) , a BiHom-Lie law \(''[,\,]''\) with degrees 0 and \(-1\) respectively over a graded vector space \(\mathfrak {g}\) . Additionally, it satisfies a compatibility condition called BiHom-Leibniz relation. Furthermore, we will provide an explicit construction of the associated BiHom-Gerstenhaber algebras up to homotopy. More precisely, this algebraic structure is defined by a structure of BiHom-cocommutative coalgebra \(\big (C,\Delta _{(f,g)},f,g\big )\) , a structure of BiHom-coLie coalgebra \(\big (C,\delta _{(f,g)},f,g\big )\) . It is equipped with a coderivation Q for two coproducts \(\Delta _{(f,g)}\) and \(\delta _{(f,g)}\) with degree 0 verifying \(Q^2=0\) and a compatibility relations, called BiHom-coLeibniz relations. This bicoalgebra is also called BiHom-Gerstenhaber algebra up to homotopy or BiHom- \(\mathfrak {g}_{\infty }\) -algebra.