Been browsing everything to do with this, and absolutely there should be a "delete history" button as per PC version.
I stumbled across something interesting which I hope helps and its a conglomeration of a few things (I have the S4!)
I found out that IF you used MSN or Windows live then you have been asked to join the 2 together?... No?.. Well I had Skype 1st and also MSN. Anyways... This is how I got rid on mine and it did take a couple of goes because it left one conversation behind.
First as per othersw, go into settings>more>app manager>skype. Then in this order: clear cache: clear data, then force stop the app. This will reset everything pasword wise.
Now go on PC. Sign in to account(s) one at a time and clear any/all history even if there appears to be none (for me was Skype and Microsoft Passport).
Sign out of both. Start up Skype again and sign in as normal.
It worked for me after a couple of goes (I think the force stop was the thing that did it!) and I have nice clean message history.
But come on Skype.. how difficult can it be to have a "clear history" button/setting....
May the force be with you!
Thanks, this also worked for me, removed all but one history from last night. Guess its just do it another time and it will go away. This is just so stupid.
4 weeks ago
I succesfully deleted history off skype on my Samsung S5.( miaybe will work for S4)
First I deleted data, cache and forece stop skype. Then uninstall it off my phone.
Reboot your phone
Next go to my computer. I have Windows 8. I push the windows button on the keyboard and "R". This brings up the run box (think you could go through the start menu on other window versions and just hit "Run")
In the box type: %appdata%. This will bring up files running data. Find skype file and delete it.
Now open skype on your computer. Erase the history through Privacy or Tools. and save it.
(I delete history twice, but that might be overkill).
Sign off and quit skype on computer.
Reinstall skype on mobile
Reboot phone again
Sign in and history should be gone.(I sometimes have "missed calls" showing, but to chats. )
Hope this helps