Where's my older Safari search history on Mac?

Also check whether you're in the right Safari profile. Newer versions of Safari let you have separate profiles (personal, work, etc.) and each one keeps its own history, so stuff can look like it vanished when it's just sitting in the other profile. The profile name shows on the toolbar if you have more than one.

History > Show All History (Cmd+Y) is the full list, not just what's in the menu, and the search box at the top searches all of it. If the older stuff isn't there, check Safari Settings > General > Remove history items. It might be set to a week or a month. Also bear in mind history syncs over iCloud, so clearing it on your phone clears it on the Mac too. Anything already gone can only come back from a Time Machine backup taken before it was removed.