removing Linux

Here’s my problem.
I am trying to reinstall Redhat on a Compaq P166mmx. I want to start fresh and remove all existence of any OS. Not being to familiar with Linux I used partion magic to remove all partitions from the HDD. When I reboot it still trys to load Red Hat and fails,no surprise since I deleted everything.
How do I wipe this disk clean and start over??? I even went as far as using partition magic to create a new FAT partion and format /s. Even after this it still try’s to load Linuxon boot up. Can somebody please tell me how to get rid of Lilo???I am a Linux newbie and not that familiar with Linux utilities.