You do not state your Joomla version, anyeay .htaccess file is a must if you want to run JoomSEF and use all its features.
If you were gettitng 404 (or 500) previously, there is most probably still some problem in the .htaccess file.
Please, go once more through the documentation and make sure all is set correctly.
ARTIO JoomSEF Documentation
Please note the example file in documentation relates to Joomla 1.0.x and in 1.5.x this is a slighly different (and easier).
The easiest way is to let JoomSEF generate the .htaccess file.
If you were getting 500 after that, just try to comment out the line Option +FollowSymLinks. That is mostly cause of this error, as some server may not support this directive.
If even after this your are getting 500 error, then make sure the mod_rewrite is enabled at your server.
If, after this the error changes to 404 make sure to set correct RewriteBase.
If you are unsure about what you are doing, you may also get an support or installation for us:
Buy ARTIO JoomSEF Installation service
Buy Joomla support services