We study how the internal structure of dark halos is affected if cold dark matter particles are assumed to have a large cross section for elastic collisions. We identify a cluster halo in a large cosmological N-body simulation and resimulate its formation with progressively increasing resolution. We compare the structure found in the two cases in which dark matter is treated as collisionless or as a fluid. For the collisionless case, the overall ellipticity of the cluster, the central density cusp, and the amount of surviving substructure are all similar to those found in earlier high-resolution simulations. Collisional dark matter results in a cluster that is more nearly spherical at all radii, has a steeper central density cusp, and has less-but still substantial-surviving substructure. As in the collisionless case, these results for a "fluid" cluster halo are expected to carry over approximately to smaller mass systems. The observed rotation curves of dwarf galaxies then argue that self-interacting dark matter can only be viable if intermediate cross sections produce structure that does not lie between the extremes we have simulated.