I tried that and it didn't work. I think you need to have Shadow beforehand, but I accidentaly destroyed him when I jumped down to my airship without him. I don't think there is any way to get Relm, Shadow, or Strago back...