The site was originally occupied by a single storey shop in 1868^[3] which was run in 1869 by Abraham Moise Josephson^[4] (who was later a successful pearl merchant).^[5] During the early 1880s the building was occupied by a branch of the National Bank of Australasia. In 1886 the branch relocated to a premises in High Street opposite Sandover's store. Later that year the building was converted into a hotel retaining the name as the National Hotel. The site and building was then owned by John J. Higham, a local merchant and businessman.^[3] William Conroy became the first landlord of the National Hotel on 6 September 1886,^[6] but ceased this occupation less than a year later when at 12:45 am on 24 June 1887 he confronted Councillor John Snook in the Fremantle Town Hall.^[7] Conroy shot Snook in the jaw. Snook subsequently died three months later. Conroy was tried and hanged for his murder.^[8][9] In 1891 Higham sold the property to Mr. James E. Hagan.^[10] In 1895 the building underwent a major reconstruction, with F. W. Welford taking over as proprietor.^[11]

The hotel was subsequently acquired by Michael and Daniel Mulcahy who came to Western Australia to prospect for gold and enjoyed great success, going on to become prominent hotel proprietors and pastoralists. In 1902 they enlisted the architect Louis Pearce to prepare plans to rebuild a more modern and commodious hotel, worthy of its position in the centre of Fremantle.

The original two storey hotel was to be replaced with a new hotel of five storeys including a basement. The hotel was to be constructed of stone and brick with stone forming the foundations and the lower portions of the walls with the brick above. The plans included a right-of-way from Market Street, and balconies totalling 140 metres (450 ft) in length and about 2.7 metres (9 ft) in width. The wall height was 14 metres (45 ft), extending to 21 metres (70 ft) from the ground to the top of the dome, the flag pole being a further 6.4 metres (21 ft) high. Internally, there was to be a total of between 50 and 60 rooms with provisions of 4.0 metres (13 ft) ceilings on the ground floor to 3.7 metres (12 ft) ceilings on the other floors as well as spacious stairways and corridors. The basement contained a large kitchen, three cellars two wine store rooms, a scullery, storeroom and servants' dining room.^[12][13]

The West Australian in 1902 stated that "The architect has, throughout, apparently, striven to produce something which will reflect the highest credit upon his profession, and when the building is completed, it should form a valuable addition to the architecture of Fremantle."^[12] The National Hotel was anticipated to cost between 7,000 and 8,000 pounds.^[12]

By 1907 M. Byrne had taken over as proprietor of the hotel.^[11]

Michael Mulcahy died in July 1917^[14] and his brother, Daniel, died in June 1925^[15] with the hotel remaining in the family ownership. By 1948 ownership had changed to Mr. T. Dean who also owned the Central Hotel in Perth.^[16]

In 1953 the building underwent further changes, and in 1975 the top floor was destroyed by fire. In 1995 the owners commenced extensive restoration work with the facade and 1st floor balconies, in 2007 while closed and nearing completion of redevelopment work the building was again set on fire resulting in substantial damage.^[17][18] In 2009 the building was sold to Carnegies, an international hospitality chain. Since then the building has been the subject of restoration efforts; the first stage reopening occurred in December 2013 with the remainder including a rooftop restaurant due towards the end of 2018.^{[needs update][1][19]}