How to remove index.php from the URL of a new install Magento Store

sudo vi .htaccess

uncomment

# RewriteBase /magento/

and change it to

RewriteBase /

Since I had a newly install version of Ubuntu web server, I needed to enable ModRewrite in apache

sudo a2enmod rewrite

Then you need to restart apache

sudo /etc/init.d/apache2 restart

Then goto your admin panel and enable the Rewrites. You can find it at System->Configuration->Web->Search Engine Optimization

Then goto Cache management page (system cache management ) and refresh your cache and refresh the Web Rewrites.