"I thought somebody had bought Europe with my credit card," said Josh Muszynski, from New Hampshire.
He says his appeals to his bank first met with little understanding, though it eventually corrected the error.
It also waived the usual $15 overdraft fee.
"It was all back to normal," Mr Muszynski told his local television station, WMUR. "They reversed the negative balance fee, which was nice."
His nightmare began when he checked his online bank account a few hours after buying the cigarettes.
When Josh Muszynski checked his bank account online, he didn't expect to find a $23 quadrillion debit.
He thought he would be a couple of hundred dollars in the black. But his overdraft had pushed him into the red - by an amount equivalent to many times the entire US national debt.
"It is a lot of money in the negative," he said. "Something I could never, ever, afford to pay back.
The 17-digit amount on his online bill shocked Mr Muszynski
"My children could not afford it, grandchildren, nothing like that."
In panic, Mr Muszynski rushed back to the petrol station, but they were unable to help. He says he then spent two hours on the phone with the Bank of America.
Eventually, it assured him it would be fixed - and the next morning, it had been.
But no-one has yet explained to Mr Muszynski how such a astonishing error could have been made.
$23 Quadrillion Question Remains Unanswered