The hydrogen membrane fuel cell (HMFC) is a new class of fuel cell in which a palladium-based thin film serves simultaneously as the anode and as a hydrogen separation membrane. The cathode consists of a perovskite ceramic and is separated from the anode by a thin layer of proton conducting ceramic. By integrating the fuel cell with a hydrogen membrane, the HMFC can generate electricity directly from hydrogen in gas mixtures produced from steam reforming renewable hydrocarbon fuels such as ethanol, eliminating the separate hydrogen purification step currently required. Here we report a simple, low cost technique to grow proton conducting ceramic crystals directly onto hydrogen membranes as thin films with nanostructure engineered to enhance performance in HMFCs. The crystals display anisotropic proton conductivity, and are grown so that the crystal axis with the highest conductivity is oriented normal to the surface of the hydrogen membrane. As a result, proton conductivity is significantly enhanced. The novel ceramic structure is characterized by electron microscopy, x-ray diffraction, and electrical impedance spectroscopy. Preliminary fuel cell performance data has been obtained that demonstrates the promise of this novel fuel cell in the temperature range of 300-600°C, temperatures intermediate between state of the art operating conditions of polymeric membranes (<200°C) and ceramic membranes (>600°C).