Abstract : Extremal optimization is an optimization technique that has been applied to a number of complex optimization problems. One such optimization problem is topology design of enterprise networks. The problem involves simultaneous optimization of a number of objectives, such as financial cost, network latency, maximum number of hops between communicating nodes in the network, and network reliability, while considering various design constraints. This paper presents an extremal optimization algorithm to efficiently solve the topology design problem of enterprise network. The multi-objective attribute of the problem is handled by incorporating goal programming in the extremal optimization algorithm. Two variants of the extremal optimization algorithm are proposed and mutually compared. Furthermore, the second variant of extremal optimization algorithm, namely, the modified extremal optimization algorithm, is also compared with the particle swarm optimization algorithm. Empirical results suggest that the modified extremal optimization algorithm produced results of higher quality than the basic extremal optimization algorithm. However, a lower level of performance was observed for the modified extremal optimization algorithm when compared with the particle swarm optimization algorithm. Keywords: Computational Intelligence, Extremal Optimization Algorithm, Goal Programming, Multi-objective Optimization, Enterprise Networks, Particle Swarm Optimization.