Methods and apparatus related to determining location of mobile devices based on signals and/or location history information received from other mobile devices are described. In various embodiments mobile devices monitor signals from other devices. Mobile devices store signal measurement information along with time stamp information and information identifying the device from which a measured signal was received. In various embodiments a mobile communications device which determines its location with reasonable accuracy, e.g., to within a predetermined distance or some other accuracy metric, transmits location history information indicating one or more past locations, and optionally the device's current location, and the times it was at the indicated locations. Reliability information is communicated with the time and location information in some embodiments. A device receiving the location history log can determine and/or refine its understanding of its own location and the location of other devices at different points in time.