[Update]The steps below are for OS X 10.10 (Yosemite). Those experiencing this because of an upgrade to 10.11 (El Capitan) seem need to only runsudo xcode-select --installas described in the accepted answer.
I know this is quite old but I got the same issue and then I fixed it by doing couple more extra steps. Problem came when Terminal could not find the actual path of the Command Line Tools.
If you had Xcode and then removed it, then Terminal is referring to
the Command Line Tools inside the Xcode folder. Try using this
command and check what your path is, xcode-select --print-path. This would most likely print /Applications/Xcode.app/Contents/Developer.
Now to fix this, reinstall the command line tools for xcode. Initially remove any previous installations using sudo rm -rf /Library/Developer/CommandLineTools.
Then install the command line tools sudo xcode-select --install
Now the final step, change the path for the CLT to the actual path using sudo xcode-select -switch /Library/Developer/CommandLineTools/ this will fix it.
It seems that upgrading from one MacOS version to another either uninstalls some dev tools or it moves them to another path, and this breaks compatibility with any tool using the environment variable that points to the old location where the tools were located.
sudo xcode-select --install
Using the install command worked for me, but it is not clear whether this simply downloaded and unpacked files and then skipped installation and simply updated an environment variable or whether it physically installed the files at the expected path. (Or it could have made links to the new folder path).
Testing my theory, I probe the folder structure with ls (I should have done this before using the install command):
It is apparent that the files are physically located at that folder location and the installer installed missing components. The fact that MacOS's upgrade process uninstalls my development environment is unfriendly and Apple should be reprimanded.
I got a similar error running Homebrew for the first time after upgrading from macOS Mojave v10.14 to Catalina v10.15.
It's never a good idea to run commands without understanding what's wrong with your installation of Homebrew and what the commands actually do. Your first and best option is to run brew doctor. This command will not only tell you if something is wrong but also how to fix the problem. In my case it showed:
Warning: Your Xcode is configured with an invalid path.
You should change it to the correct path:
sudo xcode-select -switch /Applications/Xcode.app
Once you fix the problem(s), run brew doctor again. Basically, repeat the process until you get the all clear message.
In some cases, you get something like:
Unbrewed dylibs/header files/static libraries were found in /usr/local/....
This will happen if you've installed software outside Homebrew that also use the same location to store their files. In many cases, it's safe to ignore these warnings.