According to The Atlantic, it was nearly 0 when he was elected in 1829, and on a downward trajectory. It had been under 10% since about 1800, and had been trending steadily downward since about 1820.
So if any credit is due for this accomplishment, it should probably go at least equally to his predecessors from the other party (Monroe and then John Q. Adams). Of course it is the US House of Representatives that passes all financial legislation, so technically any deficit is their doing. However, there's a legitimate case that the President's role is to provide leadership in such matters.
Digging deeper, a lot of that level seems to correlate strongly with outside factors. The upward spikes they show either correspond to major wars, or one of the two great recessions. The only serious exception to this rule appears to be the steady rise (not a spike) under the Reagan administration's implementation of supply-side economics.