Search has always been a crucial element of AI. Many aspects of what we call "intelligence" involve searching something: a physical realm, a "state space" of possible solutions, a "knowledge space" where ideas/facts/concepts/etc. are related as a graph structure, etc.
Look up some old papers on computer chess, and you'll see that a lot of that involves searching a "state space". As such, search algorithms that are efficient (in terms of time complexity and/or space complexity) have always been important to making advances there. And while computer chess is just one example, the principle generalizes to many other kinds of problem solving and goal seeking activities.
Here's a reference that explains more about some of these ideas.