On Ubuntu, I was running Python 3 and I had to install
sudo apt-get install python3-dev If you want to use a version of Python that is not linked to python3, install the associated python3.x-dev package. For example:
sudo apt-get install python3.5-dev