What fee are you talking about? If you use a debit card, and you don't have the money it will simply refuse the transaction right?
American perspective here—I feel safer using a credit card because it's not my money. If someone fraudulently bills my credit card, it's the bank that they're stealing from, not me. There are legal protections in place which limit my personal liability.
With a debit card, if someone fraudulently uses it, the money is gone and you have to fight to get it back. There are legal protections which limit my liability here too, but when I invoke those protections I'm starting from an inferior position (the money is already missing from my account), and those protections are a little better for credit cards.
Our accounts are also often reconciled with ACH, which is not as fast as it could be. So it's not always true that the transaction will be refused if you don't have the money. It's often true, but credit cards are safer because there's not really a penalty for going over your line of credit.
At the very least, I'd recommend that you have a separate debit card account that is used for store purchases and such. This gets filled (manually!) from another account which you also use only for really important stuff like utility payments, housing, car payments, etc.
Credit cards are always overdrawn in the sense that the bank has extended you a line of credit, but they don't have a fee associated with typical use.