Not wishing to argue with Schoolboy, but personally I would be inclined to install the latest version on the new server/domain first and configure it to your hearts content (and to ensure all your addons, etc are compatible) and then consider migrating your old data to the new installation.
This way you won't be messing with your live/working store while setting things up.
This process does make it a bit harder to perform the actual data migration than Schoolboys suggestion, but it also allows you to do things in a more leisurely timeframe.
One other consideration would be the number of products and customers you have. If you have a lot of data then Schoolboys recommendation is probably the way to go (just ensure you keep good backups of everything).
A 'trick' that I've found handy is after installing the latest version on the new server, is to delete the new database tables, and replace it with a backup copy of your existing database, then run the SQL upgrade scripts to bring the database back inline with the latest install. If this goes without a hitch, then you're 'home and hosed', because then you only need to deal with upgrading your templates, etc. (All the while, your existng store will still be fully operational).
Having said that, since the whole world now knows that you are running V1.3.8 it may be more prudent to take the store offline until after your upgrade, in which case, Schoolboys suggested method will be the quickest and easiest. Sad to say, but your store could be getting hacked even as I write this.
In case you didn't note, Schoolboys recommendation is more suited to more situations than my suggestion. My suggestion only comes out in front if there is no urgency for the migration and having the store offline for more than a few hours/minutes is unacceptable.
Cheers
Rod