In this paper we present a generalization of Faulhaber's formula to sums of arbitrary complex powers . These summation formulas for sums of the form and , where and , are based on a series acceleration involving Stirling numbers of the first kind. While it is well-known that the corresponding expressions obtained from the Euler-Maclaurin summation formula diverge, our summation formulas are all very rapidly convergent.