To make it simple... You use it with nouns. With verbs you leave it out. Example: Eu preciso de uma banana vs Eu preciso comer.
I admit that my translation "I have need of a horse" is a bit folksy, but I prefer it. Hopefully it will be added as acceptable.