As said in "Fiddler on the Roof" And on the other hand:

A call to Airport Information said there is no on site storage, but Airport Luggage Services will come and pick it up and deliver it. phone number is 808-372-5411. Confirming this is:
http://www.fodors.com/community/unit...lu-airport.cfm

Other info on the web:

Honolulu Baggage Storage Forum
http://www.tripadvisor.com/ShowTopic...hu_Hawaii.html

Due to enhanced airport security requirements, baggage storage and locker facilities at Honolulu International Airport are not available. Several private companies provide storage lockers in the vicinity of the airport. The airport does not endorse any of the companies but lists them as a public service. Contact the company for availability and rates.
Honolulu Baggage Storage Phone: (808) 447-9096
Aloha Airport Delivery Phone: (808) 372-5411
Alii Stor-Mor Phone: (808) 836-0135
Hawaii Self Storage Phone: (808) 836-1500
http://hawaii.gov/hnl/customer-servi...age-facilities

If you choose to use a rental car for this purpose, be very careful as car break ins are very common in some sections of Hawaii.