There are several kinds of data that can be automatically deleted when performing exit, through 'Delete data on exit' option. Browsing & download history Downloaded files Form & search history Cookies & active logins Saved passwords Cache Offline website data Site settings But none of these deletes 'Firefox Search' search history, which is a dependent but seperated search app of Firefox For Android. There should be a specific option to delete 'Firefox Search history', or just integrate 'Firefox Search' search history into 'Form & search history'.