The performance skeleton of an application is a short running program whose performance in any scenario reflects the performance of the application it represents. Such a skeleton can be employed to quickly estimate the performance of a large application under existing network and node sharing. This work presents and validates a framework for automatic construction of performance skeletons of parallel applications. The approach is based on capturing the compute and communication behavior of an executing application, summarizing this behavior and then generating a synthetic skeleton program based on the summarized information. We demonstrate that automatically generated performance skeletons take an order of magnitude less time to execute than the application they represent, yet predict the application execution time with reasonable accuracy. For the NAS benchmark suite, we observed that the average-error in predicting the execution time was 6%. This research is motivated by the problem of performance driven resource selection in shared network and Grid environments.