Stream and river monitoring have an influential role in agriculture, the fishing industry, land surveillance, the oil and gas industry, etc. Recognizing sudden changes in the behavior of streamflow could also provide tremendous insight for decision-making and administration purposes. The primary purpose of this study is to offer a new robust Regime Shift Change Detection (RSCD) algorithm which can identify periods and regime changes without any assumptions regarding the length of these periods. A regime shift algorithm using two different refined method approaches is proposed in this article. The RSCD with Relative Difference (RSCD-RD) and RSCD with Growth Rate (RSCD-GR) are the two main specializations of this regime shift algorithm. We compared these two specializations on train and test datasets and commented on the advantages and each specialization. RSCD-GR and RSCD-RD were equally effective in detecting regime changes when thresholds were pinpointed for each station and season. However, RSCD-RD outperformed RSCD-GR when general thresholds were used for cold and warm months. A strength of RSCD-GR is the ability to investigate newly observed data separately, while RSCD-RD may require re-investigation of historical data in some cases. A regime change was detected in the monthly streamflow data of the Athabasca River at Athabasca (07BE001) in May 2007, while no such change was observed in the monthly streamflow data of the Athabasca River below Fort McMurray (07DA001). The discrepancy could be attributed to factors such as the clarity of the river water from Saskatchewan or the utilization of industrial water. Additional investigation might be required to determine the underlying causes.