We report computer simulations of homogeneous gas-liquid nucleation in a model for strongly polar fluids. We find that, in the early stages of the nucleation process, chainlike clusters are formed. Beyond a certain size, these collapse to form compact spherical clusters. However, the interface of the collapsed nuclei differs markedly from the planar interface. Classical nucleation theory underestimates both the size of the critical nucleus and the height of the nucleation barrier.