Indium phosphide (InP) nanotubes have been synthesized via the vapor-liquid-solid (VLS) growth mechanism. The nanotubes are crystalline and have the (bulk) zinc blende structure and therefore represent a new class of tube materials. The tubes show photoluminescence, which is considerably blue-shifted with respect to bulk emission, indicating that the optical properties are not dominated by defect states. They are formed at higher temperatures than those at which nanowires are fabricated. A simple model for the formation of the nanotubes is presented. The wall thickness can be controlled by the synthesis temperature and is in the range of 2-20 nm.