Statens Department of Financial Services (NYDFS) sade att det ville bättre skydda konsumenterna, och förhindra penningtvätt.
Det kommer som en topp Bitcoin utbyte, Mt Gox, ansökt om konkurs förra månaden.
Bitcoins har vunnit i popularitet nyligen, men de styrs inte av någon finansiell tillsynsmyndighet.
"Faktum är att virtuella valutor sannolikt inte kommer att försvinna helt", säger Benjamin Lawsky, New Yorks överintendent för finansiella tjänster.
"Som sådan, blunda och misslyckas med att inrätta skyddsräcken för virtuella valutaföretag medan konsumenterna använder denna produkt är helt enkelt inte en hållbar strategi för tillsynsmyndigheter."
Avsaknaden av någon regleringskontroll eller tillsyn av Bitcoins har gett upphov till oro på olika fronter.
Det är svårt att spåra transaktioner som utförs med Bitcoins - en av faktorerna bakom deras popularitet - och valutan har kopplats till olaglig verksamhet på nätet.
Bitcoins ses också av vissa som en väg för skatteflykt och penningtvätt.
Ryssland har förklarat transaktioner som använder den digitala valutan olagliga, Kina har förbjudit sina banker att hantera Bitcoin handel, och det har funnits uppmaningar till USA att göra samma sak.
Singapore har infört en skatt på handel med Bitcoin och använder den för att betala för tjänster, efter att ha klassificerat den som varor, snarare än som en valuta.
Tidigare denna månad, den japanska regeringen också sagt Bitcoin är inte en valuta och att vissa transaktioner med hjälp av den virtuella enheten bör beskattas.
Fallet av Mt Gox har bara ökat oron.
Företaget ansökte om konkurs i Japan i februari efter att ha förlorat cirka $ 473m (Â £ 284m) värt kundernas bitcoins till vad det säger var en hacking attack.
"De senaste problemen vid Mt Gox och andra företag visar ytterligare det akuta behovet av en starkare tillsyn av virtuella valutaväxlingar", säger Mr Lawsky.
"Konsumenterna bör förstå och få lämpliga upplysningar om de potentiella risker som är förknippade med användning av virtuella valutor eller andra finansiella produkter."
New Yorks finansiella tillsynsmyndighet har uppmanat företag att lägga fram förslag om att inrätta "reglerade" börser för digitala valutor som Bitcoin.