In 1978, Halifax Cobequid was divided into four separate ridings, one of which was named Cole Harbour.

Upon the recommendations of the 1992 Electoral Boundaries Report, the riding was split into Cole Harbour-Eastern Passage and Dartmouth-Cole Harbour.

In 2012, following the Electoral Boundaries Commission review, this district was renamed Cole Harbour-Portland Valley and it lost a portion of the Westphal area to Preston-Dartmouth and gained the area east of Bell Lake from Dartmouth East and the Portland Hills area from Dartmouth South-Portland Valley.

[1] Following the 2019 electoral boundary review, the riding reverted back to its former name of Cole Harbour, while losing territory to the new riding of Cole Harbour-Dartmouth, exchanging some territory with Preston-Dartmouth (re-named Preston) and gaining territory from Eastern Shore and Cole Harbour-Eastern Passage.

The land area of Cole Harbour is 14 km2 (5.4 sq mi).