In a Nautilus window, click Go and Clear History.
This message is shown:

- Are you sure you want to clear the list of locations you have visited?
- If you clear the list of locations, they will be permanently deleted.

That's scary! It's just a list of locations, but the bad wording
makes it sound like the locations themselves will be
permanently deleted. Why not simplify this to a single
sentence saying:

- Are you sure you want to permanently clear the list of locations you have visited?

Or even leave out the "permanently".
Hell, it's obvious that if you clear a history, it will be lost.

Other information:
(originally: https://bugs.launchpad.net/ubuntu/+source/nautilus/+bug/260785)