How can I remove an order status I no longer use?

In Localization->Order Status I try to delete a status but Im getting the error message:
"Error: This order status is currently used in the order status history."

I have deleted all orders with the status Im trying to delete; but still Im getting this error message.