In this paper, we develop a new algorithmic framework that handles black box problems with integer variables. The strategy included in the framework makes use of specific search directions (so called primitive directions) and a suitably developed nonmonotone line search, thus guaranteeing a high level of freedom when exploring the integer lattice. We first describe and analyze a version of the algorithm that tackles problems with bound constraints. Then, we combine it with a penalty approach in order to solve problems with black box constraints. In both cases we prove finite convergence to a suitably defined local minimum of the problem (convergence to a global minimum can eventually be obtained by properly modifing a few instructions in the scheme). We report extensive numerical experiments based on a testbed of both bound constrained and generally constrained problems. We show the efficiency and robustness of the method when compared to two state-of-the-art solvers for black box optimization.