Procedures to prepare clean Bi2Se3(0001) surfaces from bulk samples and epitaxial FeSe nanocrystals on Bi2Se3(0001) are reported. Bi2Se3(0001) substrates are prepared by in vacuo cleavage of bulk samples, followed by ion bombardment and annealing cycles. FeSe is prepared by Fe deposition onto Bi2Se3 at 303K, followed by annealing at T≈623K. We use low-energy electron diffraction, surface X-ray diffraction, photoemission spectroscopy, scanning tunneling microscopy and spectroscopy, and stress measurements to elucidate the correlation between structural and electronic properties of the pristine Bi2Se3(0001) and FeSe covered surfaces. Our analysis reveals the formation of epitaxial FeSe nanocrystals with a thickness of three unit cells (1.5nm). Electron diffraction experiments indicate an anisotropic epitaxial strain in FeSe. A negligible strain close to 0.0% and a tensile strain of +2.1% are observed along the in-plane 011¯0 and 211¯0 Bi2Se3 directions, respectively. The out-of-plane strain is +4.2%. The role of this strain state for the reported high-TC superconductivity in bulk FeSe is discussed.