You can clear all history by opening the preferences and using the clear private data button. This will clear cookies, saved passwords, as well as visited sites.

If you want to only clear history you can install the clear mobile history extension. https://addons.mozilla.org/en-US/mobile/addon/clear-mobile-history/

The "Clear Private Data" button clears the history from the "History" tab. However, all of my history is still present on the "All Pages" tab. How can the data from the "All Pages" tab be deleted as well?

The "all pages" tab might be cached for a little while. It should be cleared after a few minutes, or the next time you enter a new address to navigate to in the address bar.

Unfortunately, that's not the behavior I'm seeing on my device. I cleared the history about a day ago. I've typed new URLs into the address bar since then, but all of the old entries in "All Pages" are still there.

I have the same problem. Deleting cashe and history doesn't work for me either. Any other suggestions?

I have a Droid X and I am seeing the same problem. I cleared Cache and Cleared the Data with no change to the All Pages tab. This use to work until the most recent update. I am running Firefox version 7.0.1 on a Droid X version 2.2.1.

One (not very good) workaround is to go into your device's Settings menu, then Applications -> Manage Applications -> Firefox -> Clear data. This will definitely clear the "All Pages" menu, but it will also clear everything else associated with Firefox, effectively reverting it to the state it was in right after installation. Do not do this without backing up any important data (bookmarks, saved passwords, extensions, etc.), because it will destroy everything.