"how did it all begin?"

Payroll was the very first program (well, the first business program) that Chris Hicks wrote, back in 1979 on a Commodore PET with tape drive (Incidentally, Chris sold this PET on eBay in 2006 for £50, still in working order.)

In the past 25 years the Payroll has been rewritten and modified and then rewritten again, usually several times a year. Various programmers have been involved in this work over the years, and I am sure they all feel enriched by the experience.........

As computers have got faster and more powerful, the Government has made the PAYE system bigger and more complicated, to slow things down again.