The new 10-year contract will replace contracts with EDS, which manages and updates the revenue's IT systems; and Accenture, which runs the NIRS2 National Insurance system. Both contracts run out in 2004.
Last week, an NAO report said the Revenue "almost certainly" broke EU laws when extending Accenture's contract without putting it out to tender.
The Revenue's NIRS2 system has been plagued with problems resulting in pensions backlogs and benefits miscalculations, although Accenture say it is now reliable and working well.
Inland Revenue chairman Nick Montagu said: "Our IT partner, beyond 2004, will play a major part in changing our business and we are therefore looking for the right partner with the right skills to deliver our aspirations. This tender will be vital to the future success of the Inland Revenue."
John Mackie, senior outsourcing consultant at Morgan Chambers, said: "This is a massive contract and the Revenue will look to ensure that past mistakes are not repeated. Outsourcing problems often happen in the public sector because the contracts are not put together with enough care so that everyone knows what is expected of them."