Changing from the default permalinks (?p=1) to another structure is always safe. WordPress always recognizes the default permalinks and will redirect to the canonical links.
If it's not doing that, then likely the .htaccess is broken or not being read. Make sure that the rules are in the .htaccess file, and/or contact your host.
Some cases this can be weird when you first create the .htaccess file. For example, on GoDaddy hosting, the first time you create an .htaccess, the servers don't actually use it for a couple hours. So when you enable pretty permalinks for the first time, the whole site seems to break. A couple hours later, it fixes itself. This is because of the way their hosting system works, it has to recognize the existence of .htaccess files and enable them on a per-site basis. Changes take effect instantly, it's only that initial setup that takes time.
Your host may have something similar, so even if the .htaccess is there, it may not have taken effect yet. Talk to the host about it.
If you cannot modify the .htaccess at all, then Pretty Permalinks simply will not work. Switch to a sane host.