The emergence of nano-scale memristive devices encouraged many different research areas to exploit their use in multiple applications. One of the proposed applications was to implement synaptic connections in bio-inspired neuromorphic systems. Large-scale neuromorphic hardware platforms are being developed with increasing number of neurons and synapses, having a critical bottleneck in the online learning capabilities. Spike-timing-dependent plasticity (STDP) is a widely used learning mechanism inspired by biology which updates the synaptic weight as a function of the temporal correlation between pre- and post-synaptic spikes. In this work, we demonstrate experimentally that binary stochastic STDP learning can be obtained from a memristor when the appropriate pulses are applied at both sides of the device.