The increasing use of flow cytometry (FCM) for analyses of environmental samples has resulted in a large variety of staining protocols with varying results and limited comparability. Viability assessment with FCM is in this context of particular interest because incorrect staining could severely affect the outcome/interpretation of the results. Here we propose a pipeline for the development and optimization of staining protocols for environmental samples, demonstrated with the common viability dye combination of SYBR Green I (SG) and propidium iodide (PI). Optimization steps included the assessment of dye solvents, determination of suitable PI concentration, and determining the optimal staining temperature and staining time. We demonstrated that dimethyl sulfoxide (DMSO) could impair membrane integrity, when used for SGPI stock solution preparation, and TRIS buffer was chosen as an alternative. Moreover we selected 6 μM as optimal PI final concentration: less than 3 μM resulted in incomplete staining of damaged cells, while concentrations higher that 12 μM resulted in false PI-positive staining of intact cells. Low temperatures (25 °C) resulted in a slow reaction and did not enable the staining of all bacteria, while high temperatures (44 °C) caused damage to cells and false PI-positive results. Hence, 35 °C was selected as optimal staining temperature. We further showed that a minimum of 15 min were necessary to obtain stable staining results. Moreover, we showed that addition of EDTA resulted in 1–39% more PI-positive results compared to an EDTA-free sample, and argue that insufficient evidence currently exist in favor of adding EDTA to all samples in general. Altogether, the data clearly shows the need to be careful, precise and reproducible when staining cells for flow cytometric analyses, and the need to assess and optimize staining protocols with both viable and non-viable bacteria.