Several classes of heme proteins have been identified whose primary role is to sense and transport one of the three gaseous ligands: O2, NO, or CO. A common feature shared by all of these proteins is the need to not only recognize its target ligand, but also discriminate against other heme ligands of similar size and shape. This review describes the mechanisms that each class of heme protein sensor and transporter utilizes to promote this discrimination. The common factors utilized in the recognition of each ligand are discussed.