Совсем безболезненно, к сожалению, не получится.
Необходимо составить таблицу перенаправлений. В которой прописать правила для перенаправления старого URL на новый. И реализовать ее через mod_rewrite или средствами CMS сайта.
Так пользователь, попадая на старый адрес страницы с поисковика, будет перенаправляться на новую страницу. А поисковик со временем заменит старую страницу новой.
Но если речь идет о большом количестве страниц, то просадка трафика неизбежна. В случае, если новые страницы поисковик воспримет "лучше", чем старые (оптимизация для поисковика, поведение пользователей на страницах, технические параметры скорости загрузки), то со временем трафик восстановится и станет выше!