De har satt upp önskade affischer på vandrarhem runt om i staden, som är värd vinter-OS nästa månad.
Kvinnan, 23-årig Ruzanna Ibragimova från Dagestan i norra Kaukasus regionen, tros vara änka för en islamistisk militant.
Hon tros ha halkat in i Sotji tidigare denna månad, förbi stram säkerhet före spelen.
Minst två andra potentiella kvinnliga självmordsbombare är också på fri fot i regionen, andra polisaffischer staten.
Rysslands president Vladimir Putin har inlett en av de största säkerhetsoperationerna i den olympiska historien och personligen inspekterat platserna.
Mer än 30 000 poliser och inrikesministerier har satts in och tillträdet till området är begränsat.
Säkerhetsrädsla ökade efter två självmordsbombattacker dödade 34 personer i den södra staden Volgograd den 29 och 30 december.
USA: s president Barack Obama, i ett telefonsamtal med Kreml på tisdagen, erbjöd USA: s "fullständig hjälp" för att göra OS "säkra och säkra", sade Vita huset.
Två amerikanska krigsfartyg kommer att stå i beredskap i Svarta havet när spelen börjar den 7 februari. Washington har också erbjudit sig att förse Ryssland med högteknologisk utrustning för att upptäcka improviserade sprängämnen.
Islamistiska militanter från Dagestan och närliggande republiker i Ingusjien och Tjetjenien anses av Moskva vara ett stort hot mot spelen.
Flera nationella olympiska föreningar har rapporterat att de har skickat ett e-postmeddelande som hotar idrottare med angrepp, men det avfärdades allmänt av Internationella olympiska kommittén (IOC) och nationella organ som inte trovärdiga.
IOC sade att det verkade vara "ett slumpmässigt budskap från en medlem av allmänheten", och utgjorde inget hot, men upprepade att det "tar säkerheten på största allvar".
Tjänstemän vid British Olympic Association sade att de "hämtar korrespondens av alla slag och det är inte ovanligt att stöta på något sådant som saknar trovärdighet".
"Det är oerhört viktigt i frågor som detta att alla håller en nivå huvud och ett förnuftigt perspektiv", säger talesman Darryl Seibel.
Den ryska polisen i Sotji jagar en kvinna som de fruktar planerar att genomföra en självmordsbombattack.