I haven't found any thread answering my problem, so here I am.
I've set up all the directories and files exactly as it is in the ZF QuickTutorial on the official web page. The only difference is that in my case the html dir is named "cities" - everything else is the same.
After opening the web page I get a 500 Internal Server Error.

I tried changing index.phtml to index.html, in case the server wouldn't handle the .phtml file - no effect. I know that server handles the rewrite mode. I have added the library to include_path. I'm pretty sure I've done everything ok, but it's not working. Any ideas, that might help me? Would be EXTREMELY gratefull for any kind of assistance :]

I've asked my webmaster what might the problem be, and they told me that the .htaccess entry:
RewriteRule !\.(js|ico|gif|jpg|png|css)$ index.php
is not valid on Apache 1.3.
Would anyone know, what should this entry be replaced with???

I actually tried to change the index.php to Google and it works, as in it opens the google.com page. Then I tried to remove the RewriteRule line at all, and it actually displayed the index.phtml file properly! I have no idea what is going on, and why does it work this way.

after removing RewriteRule entry from .htaccess, index.phtml was displayed properly. So I left it as it was and started working on the rest of the files. But I somehow cannot evalute <a href="<?php echo $this->baseUrl ?>/index/test">Test it</a> after putting it into index.phtml. Ofcourse baseUrl variable is set properly and I have added testAction to IndexController class, and ofcourse the test.phtml file in /application/views/scripts/index/ directory. I think this might have something to do with the fact that I don't have the RewriteRule in the .htaccess file. Am I right?

Mod_rewrite may not be enabled on your host.
You may achieve the same functionality with 404 handler and adding 200 OK header.
I am assuming that you're under Linux/Unix hosting and running apache as web server

Thanks for answer, actually it's good, that I at least know, I won't be able to use the RewriteRule. But I don't know what you mean by a 404 handler and 200 OK header. Sorry, I'm a software programmer for a few years, but actually quite new to websites programming. Would be very gratefull for explanation.