The 9/11 terrorist attacks on the core American cities shocked the world. Since then, terrorists indoctrinated by radicals, exploiting religion of Islam targeted various cities around the world such as London, Madrid, Istanbul, Jakarta, and Manila bombings to count a few. At the same time, unilateralist policies of the George W. Bush Administration triggered an unprecedented wave of anti-Americanism worldwide. More critically, unfavorable views toward the United States soared among Muslims, even in Turkey, a NATO ally since 1952. Observing these significant developments taking place simultaneously puts forward a puzzle that needs to be untangled. In search of an answer to this puzzle, I draw on Pew Key Indicators Database that surveys variables such as American image and perceptions of terrorists among Muslims. The article analyzes the relationship between those ongoing critical tendencies in world politics that are likely to have significant implications for states with predominantly Muslim populations and their relations with the Western countries.