We calculate for the first time the surface tension and curvature coefficient of a first order phase transition between two possible phases of cold nuclear matter, a normal nuclear matter phase in equilibrium with a kaon condensed phase, at densities a few times the saturation density. We find the surface tension is proportional to the difference in energy density between the two phases squared. Furthermore, we show the consequences for the geometrical structures of the mixed phase region in a neutron star.