Prior to the site's previous redevelopment in the 1960s, it had been used as the head office of the Peninsular and Oriental Steam Navigation Company (P&O) for over a century. From 1840, P&O had occupied, rent-free, the offices of Willcox & Anderson. However, business east of the Gulf of Suez increased in the late 1840s, so they needed larger offices. In November 1845, the King's Arms inn and hotel at 122 Leadenhall Street was put up for sale. P&O purchased the freehold for £7,250, and then commissioned an architect, Beachcroft, to design a new building. The cost of the new building was estimated at £8,000. In March 1848, P&O moved into the new office.