We observe long-lived tightly bound van der Waals molecules of ytterbium in a three-dimensional optical lattice with a lifetime of 8.0 s. The molecules, state-selectively produced by a photoassociation technique from a Bose-Einstein condensate or an atomic Mott insulator, are successfully detected with a photodissociation method where the molecules are photodissociated into two atoms and the atoms are captured by a magneto-optical trap or optical molasses, for the fluorescence detection. This work will open up various possibilities of research with van der Waals molecules in an optical lattice. © 2012 American Physical Society.