To me navigation and search are different things but usually placed atop a website (typical of e-commerce and SaaS products) on the "nav bar" (in html semantics by using a <nav> element)

I would first ask customer support what the biggest struggle for users currently is.

Are there too many options in the nav bar making users overwhelmed? Maybe consolidating categories is best?

Or is it that when they click a link on the nav bar they get redirected to an inappropriate page that isn't what they thought it would lead them to? Or is it the search capabilities not giving good results? What widespread implications are you thinking of? Did you basically do a complete rewrite or UI overhaul and worried users wont like it?