The use of time-of-flight (TOF) information in positron emission tomography (PET) enables significant improvement in image noise properties and, therefore, lesion detection. Silicon photomultipliers (SiPMs) are solid-state photosensors that have several advantages over photomultiplier tubes (PMTs). SiPMs are small, essentially transparent to 511 keV gamma rays and insensitive to magnetic fields. This enables novel detector designs aimed at e.g. compactness, high resolution, depth-of-interaction (DOI) correction and MRI compatibility. The goal of the present work is to study the timing performance of SiPMs in combination with LaBr3:Ce(5%), a relatively new scintillator with promising characteristics for TOF-PET. Measurements were performed with two, bare, 3 mm × 3 mm × 5 mm LaBr3:Ce(5%) crystals, each coupled to a 3 mm × 3 mm SiPM. Using a 22Na point source placed at various positions in between the two detectors, a coincidence resolving time (CRT) of ~100 ps FWHM for 511 keV annihilation photon pairs was achieved, corresponding to a TOF positioning resolution of ~15 mm FWHM. At the same time, pulse height spectra with well-resolved full-energy peaks were obtained. To our knowledge this is the best CRT reported for SiPM-based scintillation detectors to date. It is concluded that SiPM-based scintillation detectors can provide timing resolutions at least as good as detectors based on PMTs.