Data recovery from a deleted hfs+ hard drive

While working with disk utility, I accidentally deleted the (only) partition on my backup hard disk. Is there any way of recovering my data? I did not format it; just deleted the partition. Also, if I make a new partition on the drive, will all my data be there? (I am going to wait for a response before I do anything else to mess it up.) Some drive information: 500GB Seagate FreeAgent for Macintosh, GUID Partition table, 2x firewire 800 ports.

A quick response would be greatly appreciated. Thank you.

Alex Koster