Non-volatile memristors are promising for future hardware-based neurocomputation application because they are capable of emulating biological synaptic functions. Various material strategies have been studied to pursue better device performance, such as lower energy cost, better biological plausibility, etc. In this work, we show a novel design for non-volatile memristor based on CoO/Nb:SrTiO3 heterojunction. We found the memristor intrinsically exhibited resistivity switching behaviors, which can be ascribed to the migration of oxygen vacancies and charge trapping and detrapping at the heterojunction interface. The carrier trapping/detrapping level can be finely adjusted by regulating voltage amplitudes. Gradual conductance modulation can therefore be realized by using proper voltage pulse stimulations. And the spike-timing-dependent plasticity, an important Hebbian learning rule has been implemented in the device. Our results indicate the possibility of achieving artificial synapses with CoO/Nb:SrTiO3 heterojunction. Compared with filamentary-type of synaptic device, our device has potential to reduce energy consumption, realize large scale neuromorphic system, and work more reliably, since no structural distortion occurs.