Is it state or federal?
From my experience so far, and with my state (Indiana) - paid/released state tax liens stay on your credit report for seven years from the date that they are released. I have two myself. Unpaid stays indefinitely, AFAIK. The only way to have them removed is if you can have your state withdraw/expunge them. Usually that is only done if there was an error in how it was handled or recorded.
Federal liens can be withdrawn once paid, from my understanding.
