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.