Using data from Mars Global Surveyor (MGS) in combination with Particle-In-Cell (PIC) simulations of reconnection, we present the first direct evidence of collisionless magnetic reconnection at Mars. The evidence indicates that the spacecraft passed through the diffusion region where reconnection is initiated and observed the magnetic field signatures of differential electron and ion motion - the Hall magnetic field - that uniquely indicate the reconnection process. These are the first such in-situ reconnection observations at an astronomical body other than the Earth. Reconnection may be the source of Mars' recently discovered auroral activity and the changing boundaries of the closed regions of crustal magnetic field.