The permeability k and porosity \phi of vesicular basalts is measured. The relationship between k and \phi reflects the formation and emplacement of the basalts and can be related to the crystal and vesicle microstructure obtained by image analysis. Standard theoretical models relating k and \phi that work well for granular materials are unsuccessful for vesicular rocks due to the fundamental difference in pore structure. Specifically, k in vesicular rocks is governed by apertures between bubbles. The difference between calculated and measured k reflects the small size of these apertures with aperture radii typically O(10) times smaller than the mean bubble radii.