No matter how small a project is, I would always recommend having a contract in place too. I'm not sure what your fee was to do this project, but if it was a large amount and you had a contract in place, you'd have grounds to sue them for the money outstanding.

I guess we all learn these mistakes when we are first starting out, but I'll bet you'll never not ask for a deposit again