Hi Curt, just to clarify since it is possibly a 2009 make it will not have internet recovery, so performing an time machine would be ideal if you have it.
You can try all processes below, except it may be wise to reopen device and check all connections as if you were prompted with same error message could be the cable it self and not the drive as i replace many Mac and high possibility it is the hard drive or reseating the cable.
Performing the cmd+r - will boot you into the utility menu and select time machine when it appears
Though you can also press and hold the option key when your external drive is connected and be patient as it takes a bit longer than newer units. while holding the Option key only you will see three drives if any appear New hard drive, recovery drive (if any) and your external boot drive.
I have a few 2009 iMacs here and works but takes a good 30-50 seconds sometimes longer depending how much ram you may have for performance.
Finally if you have another mac or a friend with a mac you can download El Capitan 10.11.x OS X and create a bootable usb drive to boot from, but to be safe see if you have in purchases of the Mac App store or your friend to download the Mavericks version as some of the OS X's require certain ram prior to installing on the Mac.
Now this all depends on which model / year Mac that you have but a bootable Mavericks would do the trick going back to 2008 early iMac.