Composite membranes composed of highly conductive and selective layer-by-layer (LbL) films and electrospun fiber mats were fabricated and characterized for mechanical strength and electrochemical selectivity. The LbL component consists of a proton-conducting, methanol-blocking poly(diallyl dimethyl ammonium chloride)/sulfonated poly(2,6-dimethyl-1,4-phenylene oxide) (PDAC/sPPO) thin film. The electrospun fiber component consists of poly(trimethyl hexamethylene terephthalamide) (PA 6(3)T) fibers in a nonwoven mat of 60–90% porosity. The bare mats were annealed to improve their mechanical properties, which improvements are shown to be retained in the composite membranes. Spray LbL assembly was used as a means for the rapid formation of proton-conducting films that fill the void space throughout the porous electrospun matrix and create a fuel-blocking layer. Coated mats as thin as 15 μm were fabricated, and viable composite membranes with methanol permeabilities 20 times lower than Nafion and through-plane proton selectivity five and a half times greater than Nafion are demonstrated. The mechanical properties of the spray coated electrospun mats are shown to be superior to the LbL-only system and possess intrinsically greater dimensional stability and lower mechanical hysteresis than Nafion under hydrated conditions. The composite proton exchange membranes fabricated here were tested in an operational direct methanol fuel cell. The results show the potential for higher open circuit voltages (OCV) and comparable cell resistances when compared to fuel cells based on Nafion.