Destiny lists itself as "requiring an Xbox hard drive" because it requires an internal Xbox hard drive. In this particular case, it turned out that your console was the "arcade" variant, which does not come with an internal drive.
Please keep in mind that future releases will eat up more hard drive space.
Along with the core Destiny game, there are currently three DLCs1;
- The Dark Below
- The House of Wolves
- The Taken King
The Taken King can be considered more of an expansion, and brought a lot of changes to Destiny. These changes effected the vanilla version, too.
Returning players may find that the same occurrence happens with an update, as game updates are frequent, and can often add or change content.
Players that have an account registered prior to September 15, 2015, may be entitle to a free memory upgrade.
By contacting Bungie through their customer support, players may be entitle to receiving a free USB designed for their Xbox 360 or PlayStation 3, with the latest updates from The Taken King.
1At least, as of 6/4/2016.