Essential genes are responsible for the viability of an organism. Global protein interaction network analysis provides an effective way to understand the relationships between protein products of genes. By means of large-scale identification of essential genes and protein-protein interactions, we investigated the substructure of the protein interaction network in Escherichia coli and identified all the cliques in the network. Our analysis showed that larger cliques tend to have larger fractions of proteins encoded by essential genes. By merging the maximum clique with overlapping neighboring cliques, we observed a dense core of the protein interaction network in Escherichia coliwith significantly higher ratio of essential genes. The protein network of Saccharomyces cerevisiae also shows strong correlation between clique and essentiality, and there exist similar dense clusters with high essentiality. Our results indicated that the observed structure of essential cores might exist in higher organisms and play important roles in their respective protein networks.