If your nitrate is really that high, I would start with two 30% water changes a few hours apart. That should get your tank headed in the right direction. Then I would move to 50% or even 75% changes daily until you get the nitrate in control. You must use a good conditioner (like PRIME) for the new water.
Then you want to figure out why your nitrate was so high. There could a number of reasons:
- test kit wrong (you might want to try another brand as a comparison)
- lack of regular (weekly) vacuuming
- too many fish, not enough or no plants
- incoming water high in nitrates -- test that too. You might run your test kit against some distilled water as a quick check, should read 0.
Assuming your tap water is not high in nitrates, regular water changes on an ongoing basis should keep things in control. Many of us do 50% changes weekly and some even bi-weekly. Note that if you do 50% (or even higher) on a regular basis, you will NOT shock your fish since the water is being maintained at just slightly off the tape water stats, so adding tap water will not make gross changes in chemistry. You DO need a good conditioner -- many (including myself) use PRIME -- it looks expensive, but you use less than many others.