A new analytical method for the determination of both available (free and weak acid dissociable, WAD) and total cyanides in industrial wastewaters has been developed. It is based on the static headspace (HS) sampling procedure followed by a GC separation and the selective nitrogen-phosphorous detection (NPD), in which different thermal treatment allows the speciation of total and available cyanides. Detection limits (0.5 μg/L), recovery (84.7–114.6% for free and 76.8–121.5% for total cyanides) and precision (5% at 5 μg/L), evaluated on both real and synthetic samples, were fit-for-purpose for the legal requirement (5 μg/L) enforced in the Venice lagoon, without significant interfering species. In addition, analytical results of the HS-GC-NPD method have been compared with those obtained using the 4500 CN and EN ISO 14403 official methods for the determination of total and free cyanides, respectively. The new method has been successfully applied for the determination of cyanide concentrations in main influent and final effluent to the Venice lagoon to verify the efficiency of the industrial wastewater treatment plant of Porto Marghera (Venice, Italy). The capability of the proposed method to detect the WAD cyanides has been tested by studying the acid dissociation of K2[Ni(CN)4]. An unexpected speciation picture was obtained for this complex, which suggests that the present definition and analytical strategy of this cyanide class should be reconsidered.