This study examines how health literacy and mental health literacy associate with the willingness to receive a COVID-19 vaccination among American Indian/Alaska Native/Native American (AI/AN) people. Methods: The data were collected with an online Qualtrics survey in February 2021 (n = 563). A purposive snowball sampling strategy was used by sending recruitment flyers to colleagues and organizations who work with AI/AN communities to share with appropriate potential respondents. We performed linear regression analyses examining the relationships between the willingness to receive a COVID-19 vaccination and socio-demographic characteristics such as age, gender, education, health literacy, mental health literacy, self-rated physical and mental health status, worry about getting COVID-19, perceived COVID-19 susceptibility, and perceived COVID-19 severity. Results: Mental health literacy and health literacy predicted 30.90% and 4.65% of the variance (R² adjusted) in the willingness to receive a COVID-19 vaccine, respectively. After holding the self-rated physical/mental health status, worry about getting COVID-19, perceived susceptibility, perceived severity, health literacy, and socio-demographics constant, mental health literacy was still a strong predictor (b = 0.03, p < 0.001) for the willingness to receive a COVID-19 vaccine (model R² adjusted = 40.14%). Conclusions: We identified mental health literacy as a substantial factor associated with the willingness to receive a COVID-19 vaccination among AI/AN respondents.