Mint13 still has Nautilus as default. I have 13 installed on a old machine, so I fired that up and had a look, still no sign of any History at all, just Home, Computer, Templates, Rubbish Bin, Network, Location and Search. Maybe we are looking in different places, but you described it well enough, so I think I know what you are talking about. My difficulty in seeing what should be a simple answer is probably compounded by the fact that I don't use any of the default Mint file managers, Nemo, Caja or Nautilus. I still have them installed, but I hardly use them at all and haven't done for a couple of years.
Just a wild thought here (I can't check it out myself) if you right click on the Start Menu and select 'Properties' are there any settings in there that mention saving/displaying History? Just wondering if the settings in there are reflected in Nautilus?
One other thing that puzzles me (and your computer is your own business, I am not prying, you have no need to answer this if you don't want to), if you have multiple users on your computer and they each have a login then they will each have different Home folders with different histories. If you use the same login between users then what difference does displaying the history make? If another user comes along and opens you Home folder they can read anything that is in it, they don't need to consult your History to do that, so how does this improve your privacy? Don't get me wrong, I am very much concerned about privacy myself, it is just that I don't see how this will improve things.
Fujitsu Lifebook AH532. Intel i5 processor, 6Gb ram, Intel HD3000 graphics, Intel Audio/wifi. Realtek RTL8111/8168B Ethernet.Lubuntu 13.10,Ubuntu12.10 (Unity), Mint16 (Cinnamon), Manjaro (Xfce).