Pervaporation is considered the most promising technology for dehydration of bioalcohols, attracting increasing attention as a renewable energy source. In this regard, the development of stable and effective membranes is required. In this study, highly efficient membranes for the enhanced pervaporation dehydration of ethanol were developed by modification of sodium alginate (SA) with a polyethylenimine (PEI) forming polyelectrolyte complex (PEC) and graphene oxide (GO). The effect of modifications with GO or/and PEI on the structure, physicochemical, and transport characteristics of dense membranes was studied. The formation of a PEC by ionic cross-linking and its interaction with GO led to changes in membrane structure, confirmed by spectroscopic and microscopic methods. The physicochemical properties of membranes were investigated by a thermogravimetric analysis, a differential scanning calorimetry, and measurements of contact angles. The theoretical consideration using computational methods showed favorable hydrogen bonding interactions between GO, PEI, and water, which caused improved membrane performance. To increase permeability, supported membranes without treatment and cross-linked were developed by the deposition of a thin dense layer from the optimal PEC/GO (2.5%) composite onto a developed porous substrate from polyacrylonitrile. The cross-linked supported membrane demonstrated more than two times increased permeation flux, higher selectivity (above 99.7 wt.% water in the permeate) and stability for separating diluted mixtures compared to the dense pristine SA membrane.