The quality, relevance, timeliness, and impact of public health research among American Indians and Alaska Natives (AIAN) has improved markedly over the last several decades. These advances are attributable to the more careful fit between investigative methods and field exigencies, to the increased presence of Native scientists among research teams, to greater emphasis on meaningful collaboration between researchers and participating communities, and to new Federal investments in the infrastructure that supports health research within this special population. This paper describes the lessons learned from this recent progress, and highlights opportunities to promote further gains as well as continuing needs in developing our capacity to conduct policy relevant AIAN health research.