Wikipedia credits Iran (Persia) on having the first (credible) recorded postal system around 500BC.
However, I think he probably means the General Post Office (GPO) circa 1600's. It's rather sad to see the GPO site nowadays merely as a shopping portal http://www.postoffice.co.uk/portal/po.