Acabo de hacer esto ayer (tengo un MBP un poco más antiguo) y no era capaz de arrancar en el modo de recuperación de Internet sin montar la unidad antigua utilizando un trineo USB.
Según Apple, tu Mac debería ser compatible con Internet Recovery con una actualización del firmware:
https://support.apple.com/en-us/HT202313
Si por alguna razón no puedes acceder a Internet Recovery la alternativa es montar la nueva unidad externamente y usar Internet Recovery para instalar OSX en la nueva unidad antes de intercambiarlas pero el proceso de instalación será un poco más lento ya que la unidad es externa.
Espero que estés planeando instalar un SSD, yo instalé uno y supuso una gran mejora en la velocidad de mi Late 2009 MBP.