Measuring distribution of dissolved oxygen in biological tissue is of prime interest for cancer diagnosis, prognosis, and therapy optimization. Tumor hypoxia indicates poor prognosis and resistance to radiotherapy. Despite its major clinical significance, no current imaging modality provides direct imaging of tissue oxygen. We present preliminary results demonstrating the potential of photoacoustic lifetime imaging (PALI) for noninvasive, 3-D imaging of tissue oxygen. The technique is based on photoacoustic probing of the excited state lifetime of methylene blue (MB) dye. MB is an FDA-approved water soluble dye with a peak absorption at 660 nm. A double pulse laser system (pump probe) is used to excite the dye and probe its transient absorption by detecting photoacoustic emission. The relaxation rate of MB depends linearly on oxygen concentration. Our measurements show high photoacoustic signal contrast at a probe wavelength of 810 nm, where the excited state absorption is more than four times higher than the ground state absorption. Imaging of a simple phantom is demonstrated. We conclude by discussing possible implementations of the technique in clinical settings and combining it with photodynamic therapy (PDT) for real-time therapy monitoring.