Background rejection is key to success for future neutrinoless double beta decay experiments. To achieve sensitivity to effective Majorana lifetimes of $sim10^{28}$ years, backgrounds must be controlled to better than 0.1 count per ton per year, beyond the reach of any present technology. In this paper we propose a new method to identify the birth of the barium daughter ion in the neutrinoless double beta decay of $^{136}$Xe. The method adapts Single Molecule Fluorescent Imaging, a technique from biochemistry research with demonstrated single ion sensitivity. We explore possible SMFI dyes suitable for the problem of barium ion detection in high pressure xenon gas, and develop a fiber-coupled sensing system with which we can detect the presence of bulk Ba$^{++}$ ions remotely. We show that our sensor produces signal-to-background ratios as high as 85 in response to Ba$^{++}$ ions when operated in aqueous solution. We then describe the next stage of this R&D program, which will be to demonstrate chelation and fluorescence in xenon gas. If a successful barium ion tag can be developed using SMFI adapted for high pressure xenon gas detectors, the first essentially zero background, ton-scale neutrinoless double beta decay technology could be realized.