Summary form only given. Dusty or complex plasmas are plasmas containing micron-sized charged solid particulates (dust grains). Highly charged dust confined in low temperature laboratory plasmas can form two-dimensional (2D) or quasi-2D crystalline or liquid-like structures because of their mutual Coulomb repulsion. Because the structures can be easily visualized by light scattering, such strongly coupled complex plasmas are used to investigate many physics issues intrinsic to strongly coupled Coulomb systems. We propose and discuss theoretically a novel type of 2D complex plasma formed by positioning charged dust grains on the surface of liquid helium (He). Liquid He provides a nearly ideal flat substrate, has very low polarizability and conductivity, and has been used previously to study 2D systems of electrons, ions, and charged clusters. The 2D cryogenic complex plasma has possible advantages compared with traditional 2D complex plasmas. These include: (1) a more controlled environment, (2) an unscreened Coulomb interaction between the grains, (3) the possibility' that new-types of strongly coupled systems could be studied, including (a) systems composed of nanoparticles in addition to those composed of micron-size particles, (b) systems of grains placed in a strong external magnetic field, (c) systems of grains with intrinsic magnetic dipole moments, and (d) binary mixtures of grains with different charges and masses. These features could lead to new basic physics studies of new phenomena that could be explored with the 2D cryogenic complex plasma. At the same time, there are issues that require further investigation: (i) the type of grain to use, (ii) the possible use of other cryogenic liquids, (iii) methods for charging and discharging, (iv) means of confinement, (v) possible diagnostic methods, (vi) possible He transmitted damping mechanisms.