Hurray. It worked.
Deleted the file ? INIT.M ? in Frontend folder from the mentioned UserBaseDirectory. Its a bit difficult to find it in OSX.
Anyway, it worked. It cleared entire recent history, including the Cloud.
File location :
/Users/Library/Mathematica/Frontend/