Hi KaiserD2,
Give this a try and see what happens. The service name is Windows Search but even if it has been disabled, you should still see the "Search Programs and Files" box. No harm in checking though. Hit the Windows key plus r on your keyboard and type: services.msc and click OK. Scroll down until you find it and make sure the startup type is set to Automatic (Delayed Start) and the Service Status is Started. If not, click in Start and OK your change.
If the service doesn't exist, go to Programs and Features in Control Panel and click on "Turn Windows Features on or off". Scroll down, and check Windows Search. Ok, your change and reboot. Does the Search box appear when you click on Start now?
Additionally, if aforementioned doesn't resolve your issue, try turning off/disabling the above, reboot, turn on/enabling the above, reboot. Windows acts peculiar sometimes!
Have you run SFC /SCANNOW (search cmd right-click > run as administrator) you might have to run it more than once to fix corruptions)