Gallup has been named America's most Patriotic Small Town by map and atlas publisher Rand McNally. The area has a rich history of acknowledging the heroic contributions of diverse cultures. We are the home of the WWII Navajo Code Talkers and Korean War Medal of Honor Recipient Mr.