Few studies have focused on the information-seeking behaviors of archival users interested in particular cultural communities. But as community and social history are growing areas of research, it is important that archivists investigate how users identify and access relevant materials within their holdings. Of particular consideration are researchers interested in Native American communities. Collections related to Native Americans are not only dispersed across multiple indigenous and non-indigenous archives, but frequently described in ways that reflect inaccurate and outdated colonial ideologies. In this exploratory study, six archival users interested in Native American collections were interviewed about their information-seeking behaviors and research challenges. Findings from these interviews suggest several strategies for making Native-related collections more discoverable and accessible in culturally appropriate ways. Each of these strategies depends on creating and sustaining cooperative, collaborative, and mutually beneficial partnerships with Native communities.