The P. Hayman and Co. Warehouse (Former) was constructed in 1899 - 1900 as a merchandising warehouse for P. Hayman and Co. Merchants. Haymans were importers of a wide range of household goods but particularly of watches and jewellery. The company had been simultaneously established in Birmingham (as Hayman and Co.) and in Melbourne (as P. Hayman & Co.) in 1850 by brothers Louis and Philip Hayman. The Otago goldrush led P. Hayman & Co. to commence business in New Zealand in 1861 with a branch in Dunedin. Further branches were subsequently established in the other three main centres of Christchurch, Wellington and Auckland. The company commenced trading in Auckland from a leased warehouse on the south side of Customs Street East in 1883.

P. Hayman and Co. secured a 50-year lease on three adjoining lots on Customs Street East at auction in May 1898. The sites were part of the reclamation undertaken between Customs and Quay Streets over the period 1879 to 1886. As the area between Fort and Customs Streets had been reclaimed by the early 1860s, the north side of Customs Street marked the wharf frontage from this time until 1879 when the next phase of reclamation began. By 1882 much of the infill was complete, using material from Point Britomart (the site of an earlier pa). It is likely that part of the impressive stone sea wall and the 1879 foreshore lies beneath the land later developed by P. Hayman and Co. The leases of Hayman's lots (along with 16 others) had been auctioned by the Auckland Harbour Board in December 1882 and realised the highest prices in Auckland to that date for leasehold property per foot. Taken up in the boom conditions of the early 1880s these lots (and many others in the area now known as the Britomart precinct) remained vacant as development became uneconomic following the collapse of Auckland property prices in 1885. Entrepreneur Thomas Russell, lessee of Lots 94 and 95, had invested heavily in land and lost his Customs Street property in 1892. These two leases, along with that for Lot 93 - held by another party, were surrendered to the Auckland Harbour Board who put them up for auction again six years later.

Proximity to the new Railway Station (along the north side of Galway Street), the waterfront, the customhouse and the city's commercial centre made Customs Street East a desirable location for the business houses of the mercantile community when the local economy improved in the late 1890s. P. Hayman and Co. commissioned architect John Currie to design their new premises. Currie had designed L.D. Nathan's warehouse in 1897, built almost opposite the sites that Hayman's leased the following year. Nathan's warehouse, one of the largest mercantile buildings of its kind in the city, was notable for its utilisation of space and for its size and strength.

Haymans' premises, designed on similar principles, was one of a row of buildings whose construction was viewed with anticipation in the Auckland Star 's Auckland Exhibition issue of 1 December 1898. The new warehouses of uniform size were seen as representing an impressive façade on the north side of Customs Street, making a valuable addition to the town's architecture, for although Auckland had many fine public and commercial buildings, it did not convey the impression of being 'well-built'. Notwithstanding that the warehouse buildings constructed around the turn of the twentieth century represented growing prosperity, they were a source of concern for the Auckland Fire Board who viewed their innovative large cubic capacity and lack of internal brick walls as a serious risk to fire-fighters.

Completed by April 1900, Hayman's warehouse was constructed by Messrs Jones and Co. who won the tender with a price of £12,000 exclusive of fittings. The building's basement housed Hayman's packing and shipping department; the ground floor with its strong-room contained the jewellery department and counting house, and had plenty of space for a large number of clerks. The three storeys above provided accommodation for various other departments, the principal ones being crockery, drugs, musical goods, toiletries, stationery, saddlery and brush ware and the tobacconist. The principals in London, Messrs Henry and Lachman Hayman, were so pleased with report's of the architect's work that they requested their Auckland manager to select and have suitably engraved, the best watch in the establishment for Mr Currie as a token of appreciation of his professional services.

By 1934 the firm was also trading as Hayman's Open Warehouse. Alterations had been made to the ground floor entrance onto Customs Street East two years before and large display windows had been installed along an entrance arcade. Three years later, however, the leasehold was advertised for auction. Particular reference was made to the building's suitability for use as a retail shopping centre, as an increasing number of shops had become established in the immediate vicinity. Farmers' Co-operative Auctioneering Company purchased the building for £8,050. Parts were leased to tenants who by 1940 included the shipping company Port Line, notable for several 'firsts' in the trade between New Zealand and the United Kingdom. Between the 1940s and the 1960s Port Line set new trends in the styling of ships, giving rise to the era of streamlining later adopted by other shipping lines.

Towards the end of the 1960s the ground floor and basement were altered for fine art dealers, John Cordy Ltd. By this time Port Line had been joined by a number of tenants with a maritime focus including Lloyds' Register of Shipping, a master mariner and marine and cargo surveyors. In 1968 the building was sold to Columbus House Limited a company connected with the German-owned Hamburg-Sud trading as Columbus Line. Columbus Line introduced the first fully cellular container service to New Zealand in 1971. The building's interior was refurbished and a lobby with new staircase and lift was created. The building re-opened in 1970 as 'Columbus House'. By this time tenants with strong maritime connections included customs agents, travel agents and Columbus Line's local shipping agent Maritime Services Ltd, which was also the managing agent for Columbus House Ltd. Between 1984 and early 1988, the leasehold was sold several times. Leaseholders during this time included a French Polynesian shipping company Sofrana Lines, one of two companies whose vessels served the Pacific Islands. The building was known as 'Sofrana House' during this period.

In 1992 the property, along with the former Central Post Office and other land in the extended block bounded by Customs Street East, Britomart Place, Quay Street and Queen Elizabeth Square, was transferred to the Auckland City Council and Auckland Regional Council and became the site of Auckland's Britomart Transport Centre and the associated redevelopment project. The building faced an uncertain future. Following a reassessment of the project, however, Auckland City Council commissioned conservation plans for the late nineteenth/early twentieth-century buildings. These properties, with restrictive covenants imposed to protect heritage values, were on-sold to Britomart Group. Britomart Group has commenced a $350 million redevelopment project over the 5.2ha precinct. There are plans to redevelop the former P. Hayman and Co. Warehouse - along with the adjoining Barrington Building - into a boutique hotel. The property is currently (2005) vacant.