We have applied the unsharp-masking technique to the 24 µm image of the Small Magellanic Cloud (SMC), obtained with the Spitzer Space Telescope, to search for high-extinction regions. This technique has been used to locate very dense and cold interstellar clouds in the Galaxy, particularly infrared dark clouds (IRDCs). Fifty-five candidate regions of high extinction, namely, high-contrast regions (HCRs), have been identified from the generated decremental contrast image of the SMC. Most HCRs are located in the southern bar region and mainly distributed in the outskirts of CO clouds, but most likely contain a significant amount of H2. HCRs have a peak contrast at 24 µm of 2%-2.5% and a size of 8-14 pc. This corresponds to the size of typical and large Galactic IRDCs, but Galactic IRDCs are 2-3 times darker at 24 µm than our HCRs. To constrain the physical properties of the HCRs, we have performed NH3, N2H+, HNC, HCO+, and HCN observations toward one of the HCRs, HCR LIRS36-east, using the Australia Telescope Compact Array and the Mopra single-dish radio telescope. We did not detect any molecular line emission, however, our upper limits to the column densities of molecular species suggest that HCRs are most likely moderately dense with n ∼ 103/cm3. This volume density is in agreement with predictions for the cool atomic phase in low-metallicity environments. We suggest that HCRs may be tracing clouds at the transition from atomic to molecule-dominated medium, and could be a powerful way to study early stages of gas condensation in low-metallicity galaxies. Alternatively, if made up of dense molecular clumps <0.5 pc in size, HCRs could be counterparts of Galactic IRDCs, and/or regions with highly unusual abundance of very small dust grains.