We study various families of two-dimensional discrete or lattice solitons, and show that they are possible only when their power level exceeds a critical threshold. In addition, we show that gap-lattice solitons exist only when the lattice possesses a complete 2D band gap. Our results suggest that these conditions are universally valid, irrespective of the nature of the nonlinearity or the specific structure of the index lattice. The analysis explains fundamental aspects of behavior of two-dimensional discrete solitons that have been very recently observed in photosensitive optical crystals.