Yes, denitrifying bacteria require some phosphate to be present to process nitrate. However, if you feed your aquarium regularly you should have some phosphate cycling through the system, even if you can't detect it with a phosphate test kit. May, or may not, be enough for the denitrifying bacteria to hold a lower NO3 level depending on your system.
I had the same situation a while back. NO3 was up over 50 ppm, while PO4 was undetectable (Red Sea Pro Algae Management kit). I removed some excess fish to lower the bioload, lowered the amount of food (just enough to keep the fish properly fed), cut back on pellets and ReefRoid feeding of the corals and regularly removed detritus with the water changes.
Currently I have NO3 consistently reading 8-10 ppm (not bad), but am working towards ~5 ppm using low-level vinegar carbon dosing ('low-level' since I don't have much excess PO4 in the system to support a much enlarged bacterial population).
It is possible to tackle high NO3 without adding PO4 supplementation (when PO4 very low or undetectable in a system), just takes a bit longer and requires a multi-prong approach. I enjoy these kind of challenges, but understand that many reefers want to fix a problem like this as quickly as possible.
If you do add a PO4 supplement, just be careful not to over do it and test often to confirm.
