Use FDISK to delete the partition first. Then create a new one and format that. If FDISK refuses to delete (but it shouldn't) download DELPART.
Your not having a CD doesn't necessarily mean that it's an illegal OS.
I have a computer that was given to me to use as a backup. It has two small HDs: C is about 6 Gb and D is about 9 Gb. Win XP Pro is on drive C. It is set up as NTFS. The processor is about 1.5. I do not have the CD and, thus, do not want an illegal copy of XP on this computer. I have legal copies of 95, 98SE and an ME upgrade. I would like to reformat the HD to Fat32 and put on one of these older OS. However, when I try to FDISK it will not allow me to reformat the disk, apparently because it is NTFS. It has only the one partition. I've tried several things but am getting frustrated. How do I reformat this drive?