A new class of interconnection networks called the hexcube is proposed. The hexcube is similar to the base-6 generalized hypercube in structure but has a simpler interconnection scheme. The present work shows that the hexcube is vertex symmetric and possesses topological properties similar to those of the hypercube. This implies that the costs of building parallel computers using the hexcube and using the binary hypercube are similar, and are much lower than those incurred using the based-6 generalized hypercube. A one-port broadcasting algorithm for the hexcube is proposed. New results for embeddings using the hexcube as the host topology are also presented. First, a reflected Gray code-like method for finding Hamiltonian cycles is developed. Second, algorithms for all two-dimensional mesh embedding with unit expansion and a dilation of no more than two are developed. Third, it is shown that a relatively large binary hypercube can be embedded into a hexcube with a dilation of no more than three and with almost optimal expansion.