I was reading a blog post the other day that in order to upgrade from OSX Lion to OSX Mavericks you need to first upgrade to mountain lion (paying the $20 upgrade fee). Checking the description by apple as pointed out here: http://www.apple.com/osx/how-to-upgrade/
it is evident that there is no such requirement:

You can upgrade to OS X Mavericks from Snow Leopard (10.6.8), Lion (10.7), or Mountain Lion (10.8).

So, I have backed up everything and I am going to start the upgrade process now!