We report a computer-simulation study of homogeneous gas-liquid nucleation in a model for strongly polar fluids. We find that the nucleation process is initiated by chain-like clusters. As the cluster size is increased, the chains become longer. However, beyond a certain size, the nuclei collapse to form compact, spherical clusters. Nevertheless, in the interface of the collapsed nuclei a high degree of chain formation is preserved. We compare the interface of the collapsed nuclei with the planar interface and find that the interface of the globule-like nuclei differs markedly from the flat interface. Classical nucleation theory underestimates both the size of the critical nucleus and the height of the nucleation barrier.