The first parliamentary appointment of "Black Rod" came in the reign of King Henry VIII, but the post can be traced back to 1361 when the Order of the Garter was created by Edward III. The rod referred to in his title is the short ebony rod of office surmounted by a golden lion rampant which he carries.
When first created the Gentleman Usher's job was to carry this stick and "if anyone offended against the Order of the Garter it was his duty to tap him on the shoulder with the Black Rod, whereupon the offender was expelled (from the Order)." Today the rod is used to bang on the door of the House of Commons - and the damage done over many years can be clearly seen if you take a tour of the Palace.