The house was erected by R. Jones for John Gray in 1856.The first we know about John Gray is his marriage to Eliza (nee Abrahams) the widow of William Pyke in 1853. Their first child was born at Myross, Saltwater River, now Maribyrnong River. (There is now a Myross Avenue in Ascot Vale). Myross seems to have been a horse stud as the following year he won second prize for blood horses at the Port Philip Farmers’ Society Distribution of Prizes. By 1857 in time for the birth of their third child the Grays had moved into Valetta. However they decided to return to England in 1858 and put the house and its contents up for sale. In 1861 they returned and settled at Marathon, a farm near Geelong. They returned to England again 1866 where John Gray died in 1869.
The architect was Osgood Pritchard. The original two storey building comprised twelve rooms. Some demolition and rebuilding was undertaken by the subsequent owners: W.H. Hart in 1859, and C. Gray in 1862.
From 1861 to c.1865 the building was tenanted by Louis Vieusseux who operated a Ladies College.
Then Chinese importer and tea merchant, Lowe Kong Meng, was in residence until 1875. At this time the building was described as a brick house with fifteen rooms, laundry, stable and coach house. In 1875 a particularly nasty incident happened, and may have been the reason Kong Meng moved out. Two men, father and son, by the name of Rain, died when overcome by fumes as they cleaned out the cesspit at the back of the property.
Redmond Barry, Supreme Court Judge and first Chancellor of the University of Melbourne, became owner and occupier in 1879, and died there in 1880, only twelve days after the execution of Ned Kelly, over whose trial he presided.
The Vieusseux and their school returned there in 1883 when the Argus ran an expansive advertisement: LADIES' COLLEGE VALETTA HOUSE CLARENDON STREET, EAST MELBOURNE Founded 1857 Principal and Head Master-Mr L VIEUSSEUX, C.E. Scholar of the Royal Polytechnic School, Stuttgart; Diplome de l'Ecole Centrale, Paris Lady Principal- Mrs. L VIEUSSEUX Assisted by an Efficient Staff of Resident Governesses and Visiting Teachers The college comprises an elevated and healthy situation, fronting the Fitzroy Gardens. There is a large playground. The class rooms are lofty, spacious, and well lighted. All the seats are cushioned and furnished with backs. The boarders have a prívate sittingroom, containing a select library. The bedrooms are airy and commodious, the lavatory is convenient, provided with hot and cold water, plunge and shower baths. The pupils are not only taught collectively in class, but also individually, so that backward pupils receive every possible asslstance and encouragement. Terms: Payable quarterly in advance. Day pupils, 1, 2, 3, and 4 guineas Day boarders pay 2 guineas extra Resident boarders (under 13 years of age) 12 guineas Do (above 13 do), 15 guineas Quarter days for 1883 are-February 6th, April 23rd, July 24th, and October 8th Prospectuses at Mullens, Collins Street east, or at the college Principals: Mr and Mrs L VIEUSSEUX.
In 1941 a building application was submitted to the Council to build a block of flats behind the house. A three story block of nine x 2 room flats resulted. The building was given the address of 210 Albert Street and was for a time known as Doone.
From 1950 and into the 60s the property was the headquarters of the Country Fire Authority. The CFA used Valetta as its headquarters and rented the flats out to individual tenants.  The next owner was Compaq Pty Ltd who continued to rent out the flats and rented Valetta to the Australian Conservation Foundation.  In 1976 Compaq put the properties on the market and the Red Cross purchased them for its national headquarters. The Red Cross wasted no time in updating the facilities and the following year applied to build a four storey office building with car park to replace the flats at the back of Valetta. Both buildings were occupied by the Red Cross until 1998 when they were put up for sale again. The new owner converted the offices to upmarket apartments and added an extra one on top. These were strata-ed for separate sale and split off from Valetta. Valetta remains vacant and derelict.
Note:  Pre 1890 the street number was 4 Clarendon Street