Built in 1924 for the New Medway Steam Packet Company, the Medway Queen was uniquely built as a paddle steamer to specifically serve the River Medway in Kent. Constructed on the Clyde, by the Ailsa Shipbuilding Company Ltd, Maedway Queen was used to provide a pleasure service between Strood and Southend. During the Second World War, she was converted for mine sweeping duties as HMS Medway Queen for the 10th mine sweeping flotilla. The Medway Queen's finest hour was to come during the evacuation of Dunkirk in 1940, rescuing some 7000 men from its beaches. On her final journey home she was badly damaged by enemy action and was reported as lost. However, she did eventually return safely to Dover and was rightly dubbed 'the heroine of Dunkirk'.

Resuming her peacetime duties in 1947, the Medway Queen's popularity gradually declined over the years, until in the 1960s, her future was uncertain. With greater car ownership, the introduction of package holidays, and the emphasis shifting to different forms of leisure, the river excursion business was no longer a viable operation. As a result many companies folded and their ships were sold for scrap. Fortunately, the Medway Queen was saved the fate of the breaker's yard by a local public outcry, and she was subsequently purchased to become a marina clubhouse on the Isle of Wight.

Once again abandoned and derelict by the 1980s, the Medway Queen was purchased by a group of enthusiasts who brought her back to the River Medway with a plan to fully restore her. Despite their well-meaning intentions, finance and resources proved prohibitive, and Medway Queen was left a sunken wreck near Chatham dockyard.

In 1985 the newly formed Medway Queen Preservation Society (MQPS) became the new owners of the ship and began several years of restoration work. Most of this work had to be carried out in restrictive time slots, as she would be 'lost' to the murky waters again at each high tide. In time Medway Queen was eventually re-floated and moved to a more secure berth at Damhead Creek, near Hoo, where she remains today. On 30th December 1997, disaster struck again when Medway Queen sank at her moorings and, despite being successfully re-floated, she is still at serious risk due to the fragility of her hull. Only when these problems have been properly dealt with can the Medway Queen contemplate a more secure future.

After several unsuccessful attempts to acquire National Heritage Lottery funding, and with additional assistance from the Paddle Steamer Preservation Society, a £1.8m lottery grant was finally secured to completely restore the PS Medway Queen's fragile hull. In 2006 the ship was dismantled with all restorable parts being stored at both Damhead Creek and Chatham Dockyard, while tenders were sought from suitable yards to carry out the work on the hull.

On 15th October 2009 a historic moment was reached when the first section of the PS Medway Queen's new hull was laid at Albion Drydock Ltd, Bristol. This construction work will continue throughout 2010, in parallel with reconstruction of the timber parts of the ship at Damhead Creek.