Question: Who sang these boots were made for walking first?
Answer: Nancy Sinatra
Natural Questions answer: Nancy Sinatra (from the Wikipedia article "These Boots Are Made for Walkin'")