Location-based services are quickly becoming immensely popular. In addition to services based on users' current location, many potential services rely on users' location history, or their spatial-temporal provenance. Malicious users may lie about their spatial-temporal provenance without a carefully designed security system for users to prove their past locations. In this paper, we present the Spatial-Temporal provenance Assurance with Mutual Proofs (STAMP) scheme. In contrast to most existing location proof systems which rely on infrastructure like wireless APs, STAMP is based on co-located mobile devices mutually generating location proofs for each other. This makes STAMP desirable for a wider range of applications. STAMP ensures the integrity and non-transferability of the location proofs and protects users' privacy. We also examine different collusion scenarios and propose a light-weight entropy-based trust evaluation approach to detect fake proofs resulting from collusion attacks. Our prototype implementation on the Android platform shows that STAMP is low-cost in terms of computational and storage resources. Extensive simulation experiments show that our entropy-based trust model is able to achieve high (> 0.9) collusion detection accuracy.