best way to change permalinkgs

Hello WordPress forum,
I am looking for advice on permalinks. My blog currently uses the plain number links – http://www.iheartpgh.com.
I would like to switch to the links with the blog title included.
Is it possible to make this switch without breaking all of my past links.
My blog is almost 3 years old and has 930+ posts. I had a database meltdown last fall trying to upgrade the site – I was offline for weeks – so I want to make sure I am not going to break anything in the conversion.
If anyone else has made this switch before and had success I would love to hear what the best solution is.

Thanks.