Sorry to keep replying to myself. To fix this I chaged: return const_iterator(bucket_type::s_iterator_to(priv_value_to_node(const_cast<reference>(value))), this); to: return const_iterator(bucket_type::s_iterator_to(const_cast<node &>(priv_value_to_node(value))), this); in file boost/intrusive/hashtable.hpp: (near line 1682 in version 1_38_0) The original code appears to be trying to call the non-const version of priv_value_to_node() by casting away the constness of the value parameter, but it doesn't work because the 'this' pointer is still const. So, the const version of priv_value_to_node() is called instead, returning a const reference. That const reference is passed to the const version of bucket_type::s_iterator_to(), which returns a const bucket (slist) iterator. Finally, a const_iterator is constructed from the const bucket iterator, but there is no constructor to support this. The lack of supporting iterator constructor seems to be by-design, because the iterator's internal slist_it_ is always non const. Either casting away the constness of the this this pointer when calling priv_value_to_node(), or casting away the constness of the returned node reference will fix the problem. I added a const_cast to the return from priv_value_to_node() and got rid of the const_cast on the input value reference (no longer necessary). Thanks, Paul Rose