That is possible due to mod rewrite not working properly To solve this check either mod_rewrite is enabled if enabled then check your virtual host file and change it to following Often virtualhost file contains AllowOverride none that actually restricts magento .htacess files to execute. You need to put it to AllowOverride all.
Magento by default uses index.php for routing to urls. It is because some time you are on shared hosting and your apache is not configured with url rewrites = on or even on dedicated server you don't have configured apache to work with url rewrites. To remove "index.php" from magento urls you need to turn … Continue reading How to remove “index.php” from all urls in Magento