The main object of this paper is to investigate a new class of the generalized Hurwitz type poly-Bernoulli numbers and polynomials from which we derive some algorithms for evaluating the Hurwitz type poly-Bernoulli numbers and polynomials. By introducing a new generalization of the Stirling numbers of the second kind, we succeed to establish some combinatorial formulas for the generalized Hurwitz type poly-Bernoulli numbers and polynomials with negative upper indices. Moreover, we give a connection between the generalized Stirling numbers of the second kind and graph theory.