A new family of boron cross-linked graphene oxide/polyvinyl alcohol (GO-B-PVA) nanocomposite gels is prepared by freeze-thaw/boron cross-linking method. Then the gel electrolytes saturated with KOH solution are assembled into electric double layer capacitors (EDLCs). Structure, thermal and mechanical properties of GO-B-PVA are explored. The electrochemical properties of EDLCs using GO-B-PVA/KOH are investigated, and compared with those using GO-PVA/KOH gel or KOH solution electrolyte. FTIR shows that boron cross-links are introduced into GO-PVA, while the boronic structure inserted into agglomerated GO sheets is demonstrated by DMA analysis. The synergy effect of the GO and the boron crosslinking benefits for ionic conductivity due to unblocking ion channels, and for improvement of thermal stability and mechanical properties of the electrolytes. Higher specific capacitance and better cycle stability of EDLCs are obtained by using the GO-B-PVA/KOH electrolyte, especially the one at higher GO content. The nanocomposite gel electrolytes with excellent electrochemical properties and solid-like character are candidates for the industrial application in high-performance flexible solid-state EDLCs. © 2014 Elsevier Ltd.