Yes do it first, because if you take out your current drive and try to do a fresh install on a new HD it will come up with an angry face blaring at you. (There is no built in system to sort a HD out at the front end of an OS install, you can reformat it once u got the OSX loader working)
Format it now, then do fresh install.