I think it depends on the approach you take as a programmer.
If you take a top-down approach and start from the user interface and its features, then start from the Javascripts and HTML markup. In the process you can find out how your server API should respond.
If you take a "server capabilities" approach and implement what you can do in the server, then obviously you start implementing that part first. Then you'll continue with the markup and client javascript code, and adapt it to the available APIs that you built. (And probably, in the process, adapt them too).
In both cases, a bit of a design on paper wouldn't hurt.
Of course, as other people have answered, it also greatly depends on how extensive your javascript interface is, how much burden it takes away from PHP, and if you intend to provide an HTML-only interface where the PHP would need to do much of the work.
For instance, let's say you have a table in your code and you want the user to allow to sort it by different columns. This can be done in Javascript, and can be done in PHP, and it can be done in both. It's up to you and your decisions.