This assumes that you are using Lighttpd as your web server.  But this trick should work with all web servers.

If you are using Lighttpd, add the following line to your site settings in lighttpd.conf.

server.error-handler-404 = "/index.php"

You now need to restart Lighttpd.

sudo service lighttpd restart

Now login to your wp-admin console and change the permalink URL to resemble the following.

http://my-wordpress-url.com/%postname%/

That’s it!   You’re done.   The simple, easy, elegant way to get WordPress to work without showing the index.php.

Update: If you do not wish to use the 404 trick, there is another way to accomplish the same thing by using a mod_rewrite rule. The following example illustrates how to use mod_rewrite to accomplish the same thing as we did above with the 404 error handler.

url.rewrite-once = (
	"^/(wp-content|wp-includes|wp-admin|.*\.php\??).*$" => "$0" ,
	"^/((?!(index.php)).*$)" => "/index.php/$1"
)