If you don't need any info on the drive then Right click on 'My Computer' and select disk management. From there you can partition and format the drive.
Windows 7....right click 'My Computer' select manage then select disk management.
If you need the info then google search "Restore deleted partition" for some software that will restore it. There are many out there that will do this.
You may be looking in the wrong spot in (almost) the right tool. Within Computer Management you need to choose Disk Management. On the right will appear two panes (upper and lower), and each SCROLLS so you can see all it contains. The upper right pane shows all drives currently in use by Windows. But look at the LOWER RIGHT pane, which shows all connected hardware, including ones Windows can't use yet - like a HDD with no Partition. There you RIGHT-click on that drive where it says "Unallocated Space" and choose to Create and Format a Partition. Once that's done, back out and reboot so Windows can update the Registry and your drive will appear in My Computer ready to use.
Of course, this will wipe all old data from that HDD. I assume you knew that when you started by Deleting the old Partition.