We present a new black box GCD algorithm for two multivariate polynomials a and b in \(\mathbb {Z}[x_1,x_2,\dots ,x_n]\) where a and b are input as black boxes for their evaluation. Our algorithm computes \(g = \gcd (a,b)\) in the sparse representation using sparse Hensel lifting from bivariate images of g. More precisely, our algorithm first computes the square-free factorization of the primitive part of g in \(x_1\) and then, optionally, computes the content of g in \(x_1\) recursively. We have implemented our new algorithm in Maple with parts of it coded in C for increased efficiency. For comparison, we have implemented the Kaltofen–Diaz black box GCD algorithm and also a black box GCD algorithm constructed from the Kaltofen–Yang sparse rational function interpolation algorithm. Our experimental results show that our new algorithm is always competitive with the Kaltofen–Yang and Kaltofen–Diaz algorithms and faster when the square-free factors of g are smaller than g or we do not need the content of g in \(x_1\) .