The church was consecrated on December 12, 1866 and called St. Paul's Naval Church, the church was built on the shores of Esquimalt harbour just below Signal hill. The Parish served naval and army families as well as all who lived in the district up to the Point Ellis Bridge, the Gorge and Craigflower Roads, the Highlands, the Goldstream district, Colwood, Metchosin, Rocky Point, East and West Sooke and Otter Point.

In 1899 the first electric lights were installed. In 1904 the Government of Canada decided that the property on which the church stood was needed for other purposes, so the church was dismantled and moved to its present location.

The Church House, the former Gillespie home, was acquired in 1904. In World War 1 it was taken over by the army and served as a dormitory for enlisted men. The Present Parish Hall was built in 1957.

In 1911 the name of the church was changed to St. Paul's Naval and Garrison Church. This was but one of many names. It has been called, the Admiralty Church, the Esquimalt Church, the Esquimalt Episcopal Church, and the Naval Church. Today it is mostly known as St. Paul's, Esquimalt.

Upon entering the church one becomes aware of the many flags that have been "laid up" here for safekeeping. At the Chancel step  hangs the Naval Colour presented by King George VI at Beacon Hill Park when he and Queen Elizabeth visited Victoria in 1939. Across from it hanging above the memorial to Admiral Hose, the founder of the Canadian Navy, is the White Ensign which flew on HMCS Vancouver before she was paid off. Beside it hang the last Red Ensign to fly at Work Point Barracks and the Blue Ensign. These were "laid up" here in the late 1960's when the new Canadian Flag was introduced. The Blue Ensign was the Naval Jack, while the Red Ensign was the flag of Canada and the Canadian Army. Above the Lectern hangs the flag of the Royal Canadian Air Force. The colour of the Old Contemptibles, the small force that went to France in the early days of WW1, laid up here on October 12, 1975, hangs beside it. Opposite, above the Pulpit hangs the flags of the Burma Star Association of Victoria and the Chief and Petty Officers Association. Before the 3rd Battalion of the Princess Patricia's Canadian Light Infantry moved the King's and Regimental Colour of their 1st Battalion hung beside the organ.

This is only a small representation for the history that has surrounded this church over the years. There are 7 major stained glass windows, over 35 plaques dedicated to the men and woman of the Canadian Armed Forces that lost their lives in service to our great country and flags layed-up from many different forces. St. Paul's is proud of its history and proud to be part of the Royal Canadian Navy's Centennial Celebrations.