The best tool for formatting a new HDD ready for use in the Xbox is FATXplorer. It costs a one off of $30 and can be used to create Xbox and Xbox 360 drives.

If you are using an existing Xbox HDD (not a brand new one) connect the HDD to your PC using an IDE to USB adapter or directly connect it to your PC.

Open up FATXplorer and select HDD Security Tools and make sure your drive is unlocked when you select it. If this is a fresh HDD it will be, but if this is an existing Xbox HDD you will need to use the HDD Key from the EEPROM to unlock it first.

In order to use a new HDD in the Xbox it must be format ready for use.

In this example I am using a new 512GB SSD, connected to the PC using an Angelbird SATA to USB adapter.

In FATXplorer select Formatting Tools > Original Xbox HDD

Select your drive from the list, and then choose the option that makes sense for your console. If it is a stock BIOS choose the first option.

For this I am just doing a stock Xbox HDD replacement so I will select No LBA, and nothing else, and click next on all additional options. Then click Format.

Once the new drive is formatted correctly, you must now lock the drive with the HDD key extracted from the EEPROM on the console (unless it is soft/hard modded to bypass this check).

Using FATXplorer again, select HDD Security Tools, select the drive and enter the HDD Key (or Load from EEPROM) and click Set Password.

Grab HDD and use a SATA to IDE converter so you can connect the SSD/HDD up to the Xbox if using a new SATA drive, or just plug the IDE hard drive in if using an IDE hard drive.

So long as the drive was formatted correctly, and then locked with the EEPROM HDD Key, your console should accept the HDD and boot.